What is the time complexity of Max Points on a Line?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Max Points on a Line?

This problem uses Array, Hash Table, Math, Geometry. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Max Points on a Line?

Insight 1: The core idea is to iterate through each point and calculate the slope between that point and every other point. Points with the same slope from a given point lie on the same line. Insight 2: We need to handle the case where the slope is infinite (vertical lines), which occurs when the x-coordinates of two points are equal. Using `float('inf')` or a special string like "Infinity" or storing the slope as a reduced fraction (dy/dx) are common solutions.

Which companies ask LeetCode 149. Max Points on a Line in interviews?

This problem is frequently asked at Cisco, Citadel, LinkedIn, Nvidia, Oracle and 3 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Max Points on a Line - LeetCode 149 Solution

Q: How to solve Max Points on a Line?

The provided solution iterates through each point in the input array. For each point, it calculates the slope between that point and all other points. It stores the slopes in a hash map (dictionary in Python, HashMap in Java, unordered_map in C) where the key is the slope (or a representation of the slope, like a tuple of (dy, dx) after GCD reduction), and the value is the number of points with that slope. After iterating through all other points, it finds the maximum number of points that have the same slope. Finally, it updates the overall maximum number of points found so far.

Max Points on a Line - Complete Solution Guide

Max Points on a Line is LeetCode problem 149, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Given an array of points where points[i] = [x i , y i ] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line . Example 1: Input: points = [[1,1],[2,2],[3,3]] Output: 3 Example 2: Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Constraints: 1 <= points.length <= 300 points[i].length == 2 -10 4 <= x i , y i <= 10 4 All the points are unique .

Detailed Explanation

The problem asks us to find the maximum number of points that lie on the same straight line, given a set of points in a 2D plane. The input is an array of points, where each point is represented as a pair of coordinates [x, y]. The output is an integer representing the maximum number of points that lie on the same line. The constraints are that the number of points can range from 1 to 300, the coordinates are within -10000 to 10000, and all points are unique.

Solution Approach

The provided solution iterates through each point in the input array. For each point, it calculates the slope between that point and all other points. It stores the slopes in a hash map (dictionary in Python, HashMap in Java, unordered_map in C) where the key is the slope (or a representation of the slope, like a tuple of (dy, dx) after GCD reduction), and the value is the number of points with that slope. After iterating through all other points, it finds the maximum number of points that have the same slope. Finally, it updates the overall maximum number of points found so far.

Step-by-Step Algorithm

Step 1: Iterate through each point `i` in the input array `points` from index 0 to n-1.
Step 2: For each point `i`, initialize a hash map `slopes` to store the counts of slopes between `points[i]` and other points.
Step 3: Iterate through the remaining points `j` from `i+1` to n-1.
Step 4: Calculate the difference in x-coordinates `dx` and y-coordinates `dy` between `points[i]` and `points[j]`.
Step 5: If `dx` is 0, the slope is infinite (vertical line). Store this specially, either using `float('inf')` or a special string or an agreed upon value in the hashmap.
Step 6: Otherwise, calculate the greatest common divisor (GCD) of `dx` and `dy`. Simplify the slope by dividing `dx` and `dy` by their GCD. Store the simplified slope (e.g., as a tuple (dy, dx)) as the key in the `slopes` hash map, and increment the count for that slope.
Step 7: After iterating through all other points `j`, find the maximum value among the counts in the `slopes` hash map. This represents the maximum number of points that lie on a line with `points[i]` (excluding the initial point `i`).
Step 8: Update the overall maximum number of points (`max_points`) by taking the maximum between the current `max_points` and `current_max + 1` (to include the point `i` itself).
Step 9: After iterating through all points `i`, return the final `max_points`.

Key Insights

Insight 1: The core idea is to iterate through each point and calculate the slope between that point and every other point. Points with the same slope from a given point lie on the same line.
Insight 2: We need to handle the case where the slope is infinite (vertical lines), which occurs when the x-coordinates of two points are equal. Using `float('inf')` or a special string like "Infinity" or storing the slope as a reduced fraction (dy/dx) are common solutions.
Insight 3: Storing the slopes as reduced fractions (dy/dx) with the greatest common divisor (GCD) allows for accurate comparison of slopes, avoiding floating-point precision issues that could arise when using doubles for representing slopes directly.
Insight 4: The problem can be solved with O(n^2) time complexity. The maximum number of points on a line can be determined by considering each point and then checking all other points.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Math, Geometry.

Companies

Asked at: Cisco, Citadel, LinkedIn, Nvidia, Oracle, Sprinklr, Waymo, X.

Max Points on a Line | LeetCode 149

Hard

Array Hash Table Math Geometry

Time: O(n^2)Space: O(n)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }

        int max_points = 0;

        for (int i = 0; i < n; i++) {
            Map<String, Integer> slopes = new HashMap<>();
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0];
                int y1 = points[i][1];
                int x2 = points[j][0];
                int y2 = points[j][1];

                int dx = x2 - x1;
                int dy = y2 - y1;

                String slope;
                if (dx == 0) {
                    slope = "Infinity";
                } else {
                    int common_divisor = gcd(dy, dx);
                    slope = (dy / common_divisor) + "_" + (dx / common_divisor);
                }

                slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);
            }

            int current_max = 0;
            if (!slopes.isEmpty()) {
                current_max = slopes.values().stream().max(Integer::compare).get();
            }

            max_points = Math.max(max_points, current_max + 1);
        }

        return max_points;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return Math.abs(a);
        }
        return gcd(b, a % b);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 149: Max Points on a Line - Detailed explanation and solution approaches.

Topics

Array Hash Table Math Geometry

Companies

CiscoCitadelLinkedInNvidiaOracleSprinklrWaymoX

Stats

Difficulty:Hard

Languages:4

Companies:8

Problem #:149

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Iterate through each point `i` in the input array `points` from index 0 to n-1.
2
Step 2: For each point `i`, initialize a hash map `slopes` to store the counts of slopes between `points[i]` and other points.
3
Step 3: Iterate through the remaining points `j` from `i+1` to n-1.
4
Step 4: Calculate the difference in x-coordinates `dx` and y-coordinates `dy` between `points[i]` and `points[j]`.
5
Step 5: If `dx` is 0, the slope is infinite (vertical line). Store this specially, either using `float('inf')` or a special string or an agreed upon value in the hashmap.
6
Step 6: Otherwise, calculate the greatest common divisor (GCD) of `dx` and `dy`. Simplify the slope by dividing `dx` and `dy` by their GCD. Store the simplified slope (e.g., as a tuple (dy, dx)) as the key in the `slopes` hash map, and increment the count for that slope.
7
Step 7: After iterating through all other points `j`, find the maximum value among the counts in the `slopes` hash map. This represents the maximum number of points that lie on a line with `points[i]` (excluding the initial point `i`).
8
Step 8: Update the overall maximum number of points (`max_points`) by taking the maximum between the current `max_points` and `current_max + 1` (to include the point `i` itself).
9
Step 9: After iterating through all points `i`, return the final `max_points`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity arises from the nested loops. The outer loop runs 'n' times, and for each iteration, the inner loop runs approximately 'n' times, hence O(n^2). The space complexity comes from the 'slopes' hash map. In the worst case, each point will have a different slope with every other point, thus storing close to 'n' slopes, leading to O(n) space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

RANSAC (RANdom SAmple Consensus)

RANSAC is a robust method for estimating parameters of a model (in this case, a line) from a dataset containing outliers. Randomly sample two points to define a line and then count how many other points are close to that line within some tolerance. Repeat this process many times and keep the line with the most inliers.

Time: O(k*n), where k is the number of iterations and n is the number of points. It can vary a lot depending on data and iteration counts.Space: O(1) or O(n), depending on how inliers are tracked.

Trade-offs: RANSAC is more robust to outliers but has a higher overhead and is not guaranteed to find the optimal solution. The main approach is simpler to implement and more suitable if we know there aren't a lot of outliers and we require a perfect solution. RANSAC's effectiveness depends on carefully choosing the number of iterations and tolerance threshold.

✨

Key Insights

1Insight 1: The core idea is to iterate through each point and calculate the slope between that point and every other point. Points with the same slope from a given point lie on the same line.
2Insight 2: We need to handle the case where the slope is infinite (vertical lines), which occurs when the x-coordinates of two points are equal. Using `float('inf')` or a special string like "Infinity" or storing the slope as a reduced fraction (dy/dx) are common solutions.
3Insight 3: Storing the slopes as reduced fractions (dy/dx) with the greatest common divisor (GCD) allows for accurate comparison of slopes, avoiding floating-point precision issues that could arise when using doubles for representing slopes directly.
4Insight 4: The problem can be solved with O(n^2) time complexity. The maximum number of points on a line can be determined by considering each point and then checking all other points.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: Fewer than 3 points. The problem statement handles this implicitly as it just returns the number of points which is correct.
Edge case 2: Duplicate points. The problem states all points are unique. If there were duplicate points, it would affect the slope calculation, inflating counts if they are counted multiple times from different base points 'i'.
Edge case 3: Vertical lines (dx = 0). Handled by using `float('inf')` or a special string representation to represent infinite slopes, preventing division by zero.
Edge case 4: Horizontal lines (dy = 0). The GCD calculation and division by GCD will correctly handle this case, resulting in a slope of 0.
Edge case 5: Points that are very close to being on a line. Representing slopes with rational numbers (numerator and denominator) and simplifying them using GCD mitigates the issue of floating-point imprecision.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Using floating-point numbers directly for slope comparison can lead to inaccuracies due to precision issues. Simplifying slopes to reduced fractions with GCD avoids this pitfall.

✗Common mistake 2: Failing to handle the case of vertical lines (infinite slope) correctly. This can result in division-by-zero errors or incorrect slope calculations.

✗Common mistake 3: Not accounting for the starting point `i` when counting the number of points on a line. Remember to add 1 to `current_max` before updating `max_points`.

✗Common mistake 4: Integer overflow during GCD calculation. This is less likely with the given constraints but good to be aware of. Use absolute values for gcd inputs.

✗Common mistake 5: Forgetting to free the memory allocated inside maxPoints in the C code.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Image processing - Detecting lines in images (e.g., detecting lane markings on a road, finding lines in architectural drawings).

🏦Real-world scenario 2: Computer vision - Object recognition (e.g., identifying objects based on the lines that define their boundaries).

🎮Real-world scenario 3: Data analysis - Identifying trends in data by finding clusters of points that lie on a line (e.g., finding linear relationships in stock prices).

📱Real-world scenario 4: Road Mapping - Identify straight stretches of road in GPS data.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 28, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Max Points on a Line"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?