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. Consider the following Python function that checks if two rectangles overlap. What is the return value when calling isRectangleOverlap([0,0,2,2], [1,1,3,3])?

easy

A. null

B. false

C. true

D. Raises an error

Solution

1. Step 1: Calculate x_overlap

   min(2,3) - max(0,1) = 2 - 1 = 1 > 0

2. Step 2: Calculate y_overlap

   min(2,3) - max(0,1) = 2 - 1 = 1 > 0

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Both overlaps positive means rectangles overlap [OK]

Hint: Check if min > max on both axes for overlap [OK]

Common Mistakes:

• Confusing > 0 with >= 0 causing false positives on touching edges
• Mixing up coordinates leading to negative overlap
• Assuming overlap if only one axis overlaps

2. Given the following Python code to find the nth ugly number, what is the output when calling nthUglyNumber(4)?

import heapq

def nthUglyNumber(n):
    heap = [1]
    seen = {1}
    ugly = 1
    for _ in range(n):
        ugly = heapq.heappop(heap)
        for factor in [2, 3, 5]:
            new_ugly = ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)
    return ugly

print(nthUglyNumber(4))

easy

A. 6

B. 5

C. 8

D. 4

Solution

1. Step 1: Trace heap pops and pushes for n=4

   Initial heap: [1]. Iteration 1 pops 1, pushes 2,3,5. Iteration 2 pops 2, pushes 4,6,10. Iteration 3 pops 3, pushes 6 (already seen), 9, 15. Iteration 4 pops 4, pushes 8,12,20.

2. Step 2: Identify the 4th popped ugly number

   The popped numbers in order are 1, 2, 3, 4. The 4th ugly number is 4, so nthUglyNumber(4) returns 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   4 is the 4th ugly number generated by the heap [OK]

Hint: Heap pops nth ugly number in ascending order [OK]

Common Mistakes:

• Confusing the iteration count with the returned value
• Forgetting duplicates are skipped
• Miscounting the order of popped elements

3. The following code attempts to count primes less than n using an optimized sieve. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

def countPrimes(n):
    if n <= 2:
        return 0
    is_prime = [True] * (n // 2)
    is_prime[0] = False  # 1 is not prime
    for i in range(3, int(n**0.5) + 1, 2):
        if is_prime[i // 2]:
            for j in range(i, n, 2 * i):  # Bug here
                is_prime[j // 2] = False
    return 1 + sum(is_prime)  # add prime 2

medium

A. Line setting is_prime[0] = false

B. Line returning 1 + sum(is_prime)

C. Line starting the inner loop from j = i instead of i * i

D. Line checking if n <= 2 and returning 0

Solution

1. Step 1: Understand inner loop start

   The inner loop should start marking multiples from i*i, not i, to avoid redundant marking.

2. Step 2: Identify impact of bug

   Starting from i causes marking the prime number i itself as non-prime, corrupting results.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct sieve starts marking from i*i to preserve prime i [OK]

Hint: Mark multiples from i*i to avoid marking primes themselves [OK]

Common Mistakes:

• Starting marking from i instead of i*i
• Mislabeling 1 as prime
• Forgetting to add prime 2

4. What is the time complexity of the optimal rectangle overlap check algorithm that uses min and max coordinate comparisons?

medium

A. O(1), constant time since only coordinate comparisons are done

B. O(n^2), checking all pairs of points between rectangles

C. O(log n), due to sorting of coordinates

D. O(n), where n is the number of points inside the rectangles

Solution

1. Step 1: Identify operations performed

   The algorithm only performs a fixed number of min and max operations on rectangle coordinates.

2. Step 2: Recognize no loops or recursion involved

   Since no iteration over points or sorting is done, the time complexity is constant.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only a few arithmetic and comparison operations -> O(1) [OK]

Hint: No loops or recursion means O(1) time [OK]

Common Mistakes:

• Assuming complexity depends on rectangle size or points inside
• Confusing coordinate comparisons with sorting
• Thinking overlap check requires scanning all points

5. Consider the following buggy code for finding the nth ugly number. Which line contains the subtle bug that causes incorrect results for some inputs?

import heapq

def nthUglyNumber(n):
    heap = [1]
    seen = set()
    ugly = 1
    for _ in range(n):
        ugly = heapq.heappop(heap)
        for factor in [2, 3, 5]:
            new_ugly = ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)
    return ugly

medium

A. Line 3: Initializing seen as an empty set instead of containing 1

B. Line 6: Popping from heap before checking if heap is empty

C. Line 9: Multiplying ugly by factor without checking for overflow

D. Line 11: Adding new_ugly to seen before pushing to heap

Solution

1. Step 1: Check initialization of seen set

   The seen set is empty initially, but 1 is already in the heap. This causes duplicates because 1 is not marked as seen.

2. Step 2: Understand impact of missing 1 in seen

   Without 1 in seen, the algorithm may push 1 multiple times, causing duplicates and incorrect nth ugly number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding 1 to seen fixes duplicates and ensures correctness [OK]

Hint: Always mark initial heap elements as seen to avoid duplicates [OK]

Common Mistakes:

• Forgetting to add initial element to seen set
• Assuming heap uniqueness without seen tracking
• Ignoring edge cases with initial values