149. Max Points on a Line
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 differencesdx
anddy
. These represent the horizontal and vertical distances between the points. -
We then call our
gcd
function withdx
anddy
to get the greatest common divisor of the two differences,g
. -
With
g
, we normalizedx
anddy
by dividing both byg
. This step ensures we are working with the simplest form of the ratio that defines the slope. We store this normalized pair as a tuplek
. -
The
Counter
object,cnt
, updates or increments the count for the tuplek
, 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 incnt
does not include the starting point. -
After considering all pairs starting from each point
points[i]
, the final value ofans
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 EvaluatorExample 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 aCounter
object calledcnt
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 isdx = 2-1 = 1
anddy = 2-1 = 1
. We find the GCD ofdx
anddy
, 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 isdx = 3-1 = 2
anddy = 3-1 = 2
. The GCD is 2, and the normalized slope tuple is(1,1)
. We incrementcnt[(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 withcnt[(2,1)] = 1
. -
Finally for point
(1,1)
, we calculate the slope between(1,1)
and(3,2)
. The changes aredx = 3-1 = 2
anddy = 2-1 = 1
, with the GCD being 1, leading to a slope tuple(1,2)
. We putcnt[(1,2)] = 1
. -
We now compare the counter values to
ans
. For slope(1,1)
, we have 2 count, which makesans = 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 updatecnt
andans
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.
1O(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:
1O(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.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.