Max Points on a Line

📋

Problem

Imagine you are analyzing star constellations and want to find the largest group of stars that align perfectly in a straight line.

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.

1 ≤ n ≤ 10^5-10^4 ≤ x_i, y_i ≤ 10^4Points may contain duplicates

Edge cases: All points are identical → output is nAll points are vertical line → output is nPoints with negative coordinates → should handle slope sign correctly

</>

IDE

def maxPoints(points: list[list[int]]) -> int:public int maxPoints(int[][] points)int maxPoints(vector<vector<int>>& points)function maxPoints(points)

def maxPoints(points):
    # Write your solution here
    pass

class Solution {
    public int maxPoints(int[][] points) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int maxPoints(vector<vector<int>>& points) {
    // Write your solution here
    return 0;
}

function maxPoints(points) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Not counting duplicates or vertical lines properly, treating all points as distinct lines.✅ Track duplicates separately and use a special key for vertical slopes in the hash map.

Wrong: 2Greedy approach that picks first max slope without checking all points.✅ For each base point, compute slopes to all other points and find max count.

Wrong: 3Ignoring duplicates when counting max points on a line.✅ Add duplicates count to max slope count plus one for base point.

Wrong: 0Not handling empty input or single point input correctly.✅ Return 0 if input is empty; return length if input length <= 2.

Wrong: 4Floating point precision errors causing incorrect slope grouping.✅ Use gcd to reduce slope fractions to integer pairs instead of floating division.

✓

Test Cases

Focus on handling base cases like empty input and duplicates correctly.

Avoid greedy traps and ensure you check all pairs for max collinearity.

Optimize your solution to handle large inputs efficiently.

t1_01basic

Input{"points":[[1,1],[2,2],[3,3]]}

Expected3

⏱ Performance - must finish in 2000ms

All three points lie on the line y = x.

💡 Consider the slope between pairs of points to identify lines.

💡 Use a hash map to count points with the same slope relative to a base point.

💡 Remember to handle duplicates and vertical lines separately.

Why it failed: Incorrect output likely due to not counting duplicates or vertical lines properly. Fix by tracking duplicates and using a special key for vertical slopes.

✓ Correctly counts points on the same line including duplicates and vertical lines.

t1_02basic

Input{"points":[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]}

Expected4

⏱ Performance - must finish in 2000ms

Points [1,1], [3,2], [5,3], and [2,3] lie on the line with slope 0.5.

💡 Check slopes between each point and a base point to find max collinear points.

💡 Use gcd to reduce slope fractions to avoid floating point errors.

💡 Count duplicates and vertical lines separately to avoid missing points.

Why it failed: Wrong output due to floating point slope precision or ignoring duplicates. Fix by using gcd to represent slopes as reduced fractions and counting duplicates.

✓ Correctly identifies the maximum points on a line with fractional slopes.

t2_01edge

Input{"points":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input means no points, so max points on a line is 0.

💡 Check if input array is empty before processing.

💡 Return 0 immediately if no points are given.

💡 Handle empty input as a base case to avoid errors.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check for empty points and returning 0.

✓ Correctly handles empty input by returning 0.

t2_02edge

Input{"points":[[0,0]]}

Expected1

⏱ Performance - must finish in 2000ms

Single point means max points on a line is 1.

💡 If only one point, max points is 1 by definition.

💡 Check for input length <= 2 and return length directly.

💡 Handle single element as a base case.

Why it failed: Returns 0 or crashes on single point input. Fix by returning length if points length <= 2.

✓ Correctly returns 1 for single point input.

t2_03edge

Input{"points":[[1,1],[1,1],[1,1],[1,1]]}

Expected4

⏱ Performance - must finish in 2000ms

All points are identical, so max points on a line is n=4.

💡 Count duplicates carefully when points are identical.

💡 Duplicates add to the count of points on the same line.

💡 Track duplicates separately and add to max count.

Why it failed: Fails to count duplicates, returning 1 instead of 4. Fix by incrementing duplicates count when points are identical.

✓ Correctly counts all identical points as max points on a line.

t3_01corner

Input{"points":[[0,0],[0,1],[0,2],[0,3],[0,4]]}

Expected5

⏱ Performance - must finish in 2000ms

All points lie on the vertical line x=0.

💡 Vertical lines have infinite slope; handle separately.

💡 Use a special key (e.g., 'inf') for vertical slopes in the hash map.

💡 Count vertical points correctly to avoid missing max line.

Why it failed: Fails to handle vertical lines, returning less than 5. Fix by using a special slope key for vertical lines.

✓ Correctly counts all points on vertical line.

t3_02corner

Input{"points":[[1,1],[2,2],[3,3],[4,5],[5,7]]}

Expected3

⏱ Performance - must finish in 2000ms

Points [1,1],[2,2],[3,3] lie on line y=x; others do not align with them.

💡 Beware of greedy approaches that pick first max slope without checking all points.

💡 Check all pairs to find global max, not just local max per point.

💡 Use nested loops or hash map per base point to find max collinear points.

Why it failed: Greedy approach fails by returning 2 instead of 3. Fix by checking all points relative to each base point.

✓ Correctly finds max points on a line by checking all pairs.

t3_03corner

Input{"points":[[1,1],[2,2],[3,3],[1,1],[2,2]]}

Expected5

⏱ Performance - must finish in 2000ms

Duplicates of points on line y=x increase max count to 5.

💡 Handle duplicates carefully to avoid undercounting.

💡 Add duplicates count to max slope count plus one for base point.

💡 Use gcd to reduce slope fractions and count duplicates separately.

Why it failed: Fails to add duplicates, returning 3 instead of 5. Fix by incrementing duplicates count and adding to max count.

✓ Correctly counts duplicates on the same line.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(n^2) brute force time complexity; must complete within 2 seconds.

💡 Brute force O(n^2) will time out for large n.

💡 Use hashing with reduced fraction slopes to optimize counting.

💡 Consider early termination or pruning to improve performance.

Why it failed: TLE due to O(n^2) complexity on large input. Fix by optimizing slope calculation and using hash maps efficiently.

✓ Algorithm runs within time limit confirming O(n^2) optimized approach.

Practice

1. What is the time complexity of answering a single query using the precomputed lookup table approach for the angle between clock hands, assuming the table is already built?

medium

A. O(1) because the angle is retrieved directly from a precomputed 12x60 table.

B. O(12*60) because you must compute all angles each query.

C. O(60) because you must scan all minutes to find the angle.

D. O(log(720)) because binary search is used on the precomputed angles.

Solution

1. Step 1: Understand precomputation

   The table stores angles for all 12 hours and 60 minutes, total 720 entries, computed once.

2. Step 2: Query time complexity

   Each query accesses the table by hour and minute indices directly, which is constant time O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Lookup table access is direct indexing -> O(1) [OK]

Hint: Precomputation shifts cost to setup, queries are O(1) [OK]

Common Mistakes:

• Confusing precomputation cost with query cost
• Assuming linear scan or binary search needed per query

2. Consider the following buggy code snippet for converting an Excel column title to a number. Which line contains the subtle bug that causes incorrect results for inputs like "A" or "Z"?

medium

A. Line 4: powers computation loop

B. Line 7: initialization of result

C. Line 9: calculation of value using zero-based indexing

D. Line 10: accumulation of result using powers

Solution

1. Step 1: Identify how letter values are computed

   The code uses ord(ch) - ord('A'), which makes 'A' = 0 instead of 1.

2. Step 2: Understand impact on result

   This causes all results to be off by one, e.g., "A" returns 0 instead of 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct letter values must be 1-based, not zero-based [OK]

Hint: Check if 'A' maps to 1, not 0 [OK]

Common Mistakes:

• Using zero-based indexing for letters
• Miscomputing powers array
• Incorrect accumulation order

3. The following code attempts to check if an integer is a palindrome by reversing half of its digits. Which line contains a subtle bug that causes incorrect results for inputs like 10 or negative numbers?

medium

A. Line 6: return x == reversed_half or x == reversed_half // 10

B. Line 2: reversed_half = 0

C. Line 1: def is_palindrome(x: int) -> bool:

D. Line 3: while x > reversed_half:

Solution

1. Step 1: Identify missing edge case handling

   Negative numbers and numbers ending with zero (except zero itself) are not handled before the loop.

2. Step 2: Analyze loop condition

   Without checking negatives or trailing zeros, the loop condition allows incorrect inputs to proceed, causing wrong results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding pre-check for negatives and trailing zeros before loop fixes bug [OK]

Hint: Check input constraints before main logic to avoid subtle bugs [OK]

Common Mistakes:

• Ignoring negative input check
• Not handling trailing zeros
• Assuming loop condition suffices

4. Consider this buggy recursive reverse integer code snippet:

def reverse(x: int) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    sign = -1 if x < 0 else 1
    x = abs(x)

    def helper(num, rev):
        if num == 0:
            return rev
        pop = num % 10
        # Bug: Missing overflow check here
        rev = rev * 10 + pop
        return helper(num // 10, rev)

    rev = helper(x, 0)
    return sign * rev if rev != 0 else 0

What is the root cause of incorrect behavior in this code?

medium

A. Line 'rev = rev * 10 + pop' lacks overflow check before multiplication

B. Line with 'sign = -1 if x < 0 else 1' does not handle zero correctly

C. Line 'pop = num % 10' incorrectly extracts digits for negative numbers

D. Line 'return sign * rev if rev != 0 else 0' returns zero incorrectly for valid reversed zero

Solution

1. Step 1: Identify missing overflow check

   The code multiplies rev by 10 and adds pop without checking if rev will overflow 32-bit integer limits.

2. Step 2: Consequence of missing check

   Without overflow check before multiplication, the reversed integer can exceed INT_MAX causing incorrect results or runtime errors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overflow check must precede rev update to avoid errors [OK]

Hint: Overflow check must happen before rev update [OK]

Common Mistakes:

• Ignoring overflow before multiplying rev by 10
• Assuming sign handling fixes overflow
• Misunderstanding digit extraction for negatives

5. Suppose you want to extend the happy number check to negative integers by applying the same digit square sum process on their absolute values. Which modification to the algorithm is necessary to correctly handle negative inputs?

hard

A. Add a check to convert negative input to positive before processing digits.

B. Modify digit extraction to handle negative digits directly without conversion.

C. Use recursion instead of iteration to handle negative inputs.

D. No modification needed; the existing algorithm works for negative numbers.

Solution

1. Step 1: Understand digit extraction for negatives

   Digit extraction using modulo and division assumes non-negative numbers; negative digits do not exist.

2. Step 2: Convert negative input to positive

   Taking absolute value ensures digit extraction works correctly and the sum of squares is computed properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Absolute value conversion fixes digit extraction for negatives [OK]

Hint: Digit extraction requires non-negative numbers [OK]

Common Mistakes:

• Trying to extract digits from negative directly
• Assuming recursion helps
• Ignoring sign issues