149. Max Points on a Line

HardGeometryArrayHash TableMath

Problem Description

The problem presents a set of points on a 2D coordinate system and asks us to find the maximum number of points that align straightly. In simple terms, we are to determine the largest group of points that lie on the same line. This is a geometric problem commonly encountered in computer graphics and spatial analysis and has significant implications in understanding patterns and relationships between data points in a 2D space.

Intuition

The intuition behind the solution begins with the realization that to find points on the same line, we need to consider the slope formed by pairs of points. In mathematics, the slope of a line is a number that describes both the direction and the steepness of the line.

The key idea for this solution is to iterate through each point and calculate slopes it forms with all other points. If two different lines share the same slope and have a common point, it means they are the same line. However, calculating slopes as floating-point numbers can cause precision issues. To circumvent this, we represent slopes as fractional tuples (dy, dx) where dy is the change in y (rise) and dx is the change in x (run).

Before creating this tuple, we need to reduce these values to their simplest form so that the slopes are uniformly represented. This is where the greatest common divisor (GCD) comes in: if we divide both dy and dx by their GCD, we get the smallest identical tuple for all points on the same line.

As we calculate these slope tuples, we store and count them using a hash structure, a Counter in Python, which keeps the count of each distinct slope seen from a specific starting point. The maximum count of these slopes, plus 1 (for the starting point itself), will indicate the maximum number of points on the same line from that point. We track the overall maximum as we loop through each point to solve the problem.

Learn more about Math patterns.

Solution Approach

The solution uses a brute-force approach along with some mathematical optimizations to reduce computational complexity. Below is the step-by-step breakdown of the implementation:

The gcd function is defined to find the greatest common divisor of two numbers. It's a classic algorithm known as Euclid's algorithm, which is a recursive approach to successively finding remainders until it lands a zero, thereby finding the GCD of the initial pair.
We start by initializing the ans to 1 which represents the default maximum number of points on a line that can always include the point itself.
We iterate over each point points[i] in the outer loop. This point will act as a reference or starting point to calculate slopes with every other point.
For a given reference point, we create a Counter object to keep track of all the slopes we calculate from the reference point to all other points.
The inner loop starts from points[i + 1] to the end of the array, ensuring we don't repeat calculations for pairs of points that we have already checked.
For every point points[j] in this inner loop, we calculate the differences dx and dy. These represent the horizontal and vertical distances between the points.
We then call our gcd function with dx and dy to get the greatest common divisor of the two differences, g.
With g, we normalize dx and dy by dividing both by g. This step ensures we are working with the simplest form of the ratio that defines the slope. We store this normalized pair as a tuple k.
The Counter object, cnt, updates or increments the count for the tuple k, effectively counting how many points have formed the exact same slope with the starting point.
As we increment the count, we also keep track of the maximum value so far with ans = max(ans, cnt[k] + 1). We add 1 because the count in cnt does not include the starting point.
After considering all pairs starting from each point points[i], the final value of ans will be the maximum number of points that lie on the same line.

This approach is exhaustive in that it compares all pairs, but it's efficient in ensuring the numerical stability and uniqueness of the slopes by using the GCD and normalizing the differences. Although the time complexity can be high for very large input arrays, this method is quite practical and straightforward when dealing with typical problem constraints seen in coding interviews.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's consider a small example. Suppose we have the following set of points on a 2D coordinate system: [(1,1), (2,2), (3,3), (2,3), (3,2)].

We begin by initializing ans to 1.
Starting with the first point, (1,1), we create a Counter object called cnt to store the slopes of lines formed with this point and others.
We skip comparing (1,1) with itself and move on to calculate the slope with the second point (2,2). The change is dx = 2-1 = 1 and dy = 2-1 = 1. We find the GCD of dx and dy, which is 1, and normalize to get the slope tuple (dy/dx) = (1/1).
We update the counter by setting cnt[(1,1)] to 1, indicating that there's one line with this slope from the start point.
Next, we calculate the slope between (1,1) and (3,3). The change is dx = 3-1 = 2 and dy = 3-1 = 2. The GCD is 2, and the normalized slope tuple is (1,1). We increment cnt[(1,1)] to 2.
Now, we check the slope between (1,1) and (2,3). Here, dx = 2-1 = 1, dy = 3-1 = 2. The GCD is 1, so the tuple becomes (2,1). We store this new slope in the counter with cnt[(2,1)] = 1.
Finally for point (1,1), we calculate the slope between (1,1) and (3,2). The changes are dx = 3-1 = 2 and dy = 2-1 = 1, with the GCD being 1, leading to a slope tuple (1,2). We put cnt[(1,2)] = 1.
We now compare the counter values to ans. For slope (1,1), we have 2 count, which makes ans = max(1, 2+1) (we add 1 to include the reference point).
Repeat the process from points (2,2), (3,3), (2,3), and (3,2). Each time we update cnt and ans appropriately.

Upon completing the loops, we find that the slope (1,1) has the highest count, thus the maximum number of points aligning straightly is ans, which now equates to 3, taken from the three collinear points (1,1), (2,2), and (3,3).

This step-by-step iteration through each point and counting slope occurrences provides us with the required result. This approach will be applied to all points and all possible slopes to ensure we find the maximum number of collinear points.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def maxPoints(self, points):
5        """
6        Calculates the maximum number of points that lie on a straight line.
7      
8        :param points: A list of point coordinates [x, y].
9        :type points: List[List[int]]
10        :return: The maximum number of points on a straight line.
11        :rtype: int
12        """
13      
14        def calculate_gcd(a, b):
15            """
16            Helper function to calculate the Greatest Common Divisor (GCD) using recursion.
17          
18            :param a: First number
19            :param b: Second number
20            :return: GCD of a and b
21            """
22            return a if b == 0 else calculate_gcd(b, a % b)
23      
24        num_points = len(points)
25        max_points_on_line = 1  # A single point is always on a line.
26      
27        for i in range(num_points):
28            x1, y1 = points[i]
29            slopes = Counter()  # Counter to track the number of points for each slope
30            for j in range(i + 1, num_points):
31                x2, y2 = points[j]
32                delta_x = x2 - x1
33                delta_y = y2 - y1
34                gcd_value = calculate_gcd(delta_x, delta_y)
35              
36                # Reduce the slope to its simplest form to count all equivalent slopes together.
37                slope = (delta_x // gcd_value, delta_y // gcd_value)
38              
39                # Increment the count for this slope and update the maximum if needed.
40                slopes[slope] += 1
41                max_points_on_line = max(max_points_on_line, slopes[slope] + 1)
42              
43        return max_points_on_line
44
45# An example of using the class to calculate the maximum number of points on a line.
46# Example usage:
47# solution = Solution()
48# result = solution.maxPoints([[1,1], [2,2], [3,3]])
49# print(result)  # Output: 3
50

1class Solution {
2    public int maxPoints(int[][] points) {
3        // Number of points on the plane
4        int numPoints = points.length;
5        // At least one point will always form a line
6        int maxPointsInLine = 1;
7      
8        // Iterate over all points as the starting point of a line
9        for (int i = 0; i < numPoints; ++i) {
10            int x1 = points[i][0], y1 = points[i][1];
11            // A map to store the slope of lines and their counts
12            Map<String, Integer> lineMap = new HashMap<>();
13          
14            // Try forming lines with every other point
15            for (int j = i + 1; j < numPoints; ++j) {
16                int x2 = points[j][0], y2 = points[j][1];
17                // Calculate the deltas for the line
18                int deltaX = x2 - x1;
19                int deltaY = y2 - y1;
20                // Compute the greatest common divisor to normalize the slope
21                int gcd = gcd(deltaX, deltaY);
22                // Create a unique string key for the slope after normalizing
23                String slopeKey = (deltaX / gcd) + "." + (deltaY / gcd);
24                // Increment the number of points that form the current line
25                lineMap.put(slopeKey, lineMap.getOrDefault(slopeKey, 0) + 1);
26                // Update the maximum number of points in a line if necessary
27                maxPointsInLine = Math.max(maxPointsInLine, lineMap.get(slopeKey) + 1);
28            }
29        }
30        // Return the maximum number of points found in a line
31        return maxPointsInLine;
32    }
33
34    // Helper method to calculate the greatest common divisor of two numbers
35    private int gcd(int a, int b) {
36        return b == 0 ? a : gcd(b, a % b);
37    }
38}
39

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <algorithm>
5
6class Solution {
7public:
8    // Helper function to find the Greatest Common Divisor (GCD) of two numbers
9    int gcd(int a, int b) {
10        return b == 0 ? a : gcd(b, a % b);
11    }
12
13    // Function to find the maximum number of points that lie on a straight line
14    int maxPoints(std::vector<std::vector<int>>& points) {
15        int numPoints = points.size(); // Number of points
16        int maxPointsOnLine = 1; // Initialize the maximum with 1 (a line requires at least 2 points)
17
18        for (int i = 0; i < numPoints; ++i) {
19            int x1 = points[i][0], y1 = points[i][1]; // Coordinates for the first point
20            std::unordered_map<std::string, int> slopeCount; // Map to keep track of slopes (as string keys) and their counts
21          
22            for (int j = i + 1; j < numPoints; ++j) {
23                int x2 = points[j][0], y2 = points[j][1]; // Coordinates for the second point
24                int deltaX = x2 - x1, deltaY = y2 - y1; // Differences in x and y coordinates (components of the slope)
25                int gcdSlope = gcd(deltaX, deltaY); // Calculate GCD to standardize the slope
26
27                // Create a unique key for the slope by concatenating deltaX and deltaY divided by their GCD
28                std::string slopeKey = std::to_string(deltaX / gcdSlope) + "." + std::to_string(deltaY / gcdSlope);
29
30                // Increment the count of points for the current slope
31                slopeCount[slopeKey]++;
32                // Update maxPointsOnLine if the current slope has more points than the maximum recorded so far
33                maxPointsOnLine = std::max(maxPointsOnLine, slopeCount[slopeKey] + 1);
34            }
35        }
36        return maxPointsOnLine; // Return the maximum number of points on a line
37    }
38};
39

1// Import statements from TypeScript/JavaScript are not required here as we're defining global variables and methods.
2
3// Helper function to find the Greatest Common Divisor (GCD) of two numbers
4function gcd(a: number, b: number): number {
5    // If b is 0, a is the GCD
6    return b === 0 ? a : gcd(b, a % b);
7}
8
9// Function to find the maximum number of points that lie on a straight line
10function maxPoints(points: number[][]): number {
11    const numOfPoints = points.length; // Number of points
12    let maxPointsOnLine = 1; // Initialize to 1 since a single point technically forms a line
13
14    // Iterate through each point to use as a starting point
15    for (let i = 0; i < numOfPoints; ++i) {
16        const x1 = points[i][0], y1 = points[i][1]; // Coordinates for the current point
17        let slopeCount: { [key: string]: number } = {}; // Map to keep track of slopes and their counts
18      
19        // Iterate through remaining points to form lines and calculate slopes
20        for (let j = i + 1; j < numOfPoints; ++j) {
21            const x2 = points[j][0], y2 = points[j][1]; // Coordinates for the next point
22            let deltaX = x2 - x1, deltaY = y2 - y1; // Differences in x and y coordinates (components of the slope)
23            const commonDivisor = gcd(deltaX, deltaY); // Calculate GCD to standardize the slope representation
24
25            // Create a unique key for the slope by concatenating normalized deltaX and deltaY
26            const slopeKey = `${deltaX / commonDivisor},${deltaY / commonDivisor}`;
27
28            // Increment the count of points for the current normalized slope
29            slopeCount[slopeKey] = (slopeCount[slopeKey] || 0) + 1;
30            // Update maxPointsOnLine if the current slope has more points than the maximum recorded so far
31            maxPointsOnLine = Math.max(maxPointsOnLine, slopeCount[slopeKey] + 1);
32        }
33    }
34
35    return maxPointsOnLine; // Return the maximum number of points on a line
36}
37
38// Example usage:
39// const result = maxPoints([[1,1],[2,2],[3,3]]);
40// console.log(result); // Output would be 3
41

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by two nested loops iterating over the points and the calculation of the greatest common divisor (gcd) for each pair of points. The outer loop runs n times (where n is the number of points), and the inner loop runs progressively fewer times as i increases, leading to a sum of the series from 1 to n-1, which is (n-1)n/2. The gcd calculation has a time complexity that is generally O(log(min(a, b))), where a and b are the differences in the x and y coordinates of two points.

Overall, the time complexity is O(n^2 * log(min(dx, dy))), since the gcd computation is the most significant operation in the inner loop.

O(n^2 * log(min(dx, dy)))

Space Complexity

The space complexity of the code is largely influenced by the Counter dictionary storing each unique slope encountered. In the worst case, every pair of points could have a unique slope, leading to O(n^2) entries in the Counter. However, this is very unlikely in a standard dataset, and thus the space complexity would typically be much lower.

The recursive nature of the gcd function also adds to the space complexity, due to the call stack. However, because the depth of the recursion is O(log(min(a, b))), this does not significantly affect the overall space complexity.

Thus, the worst-case space complexity is:

O(n^2)

But on average, it would be significantly better, depending on how many points share the same slope.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?

Stack

Queue

Tree

Linked List

I don’t know