Max Points on a Line

▶

Steps

setup

Initialize and Sort Points

The algorithm starts by sorting the points to enable early termination and easier slope calculations.

💡 Sorting ensures points are processed in order, which helps optimize the search for the maximum points on a line.

Line:

n = len(points)
if n <= 2:
    return n
points.sort()

💡 Sorting the points is a crucial preprocessing step that simplifies later comparisons.

traverse

Start Outer Loop with i=0

Set pointer i to the first point [1,1]. This point will be the base for slope calculations.

💡 Choosing a base point allows us to calculate slopes to all other points and find lines passing through it.

Line:

for i in range(n):

💡 The outer loop iterates through each point as a potential line anchor.

prune

Check Early Termination Condition for i=0

Check if max_points (1) is >= n - i (3 - 0 = 3) or max_points > n//2 (1 > 1). Condition false, continue.

💡 Early termination avoids unnecessary work if no better line can be found.

Line:

if max_points >= n - i or max_points > n // 2:
    break

💡 Early termination condition is a performance optimization, not affecting correctness.

setup

Initialize Slopes and Duplicates for i=0

Create an empty hashmap for slopes and set duplicates count to zero for the base point [1,1].

💡 Tracking slopes and duplicates helps count points on the same line efficiently.

Line:

slopes = defaultdict(int)
duplicates = 0

💡 Resetting counters for each base point is necessary to isolate slope counts.

traverse

Start Inner Loop with j=1

Set pointer j to the second point [2,2] to calculate slope with base point [1,1].

💡 Comparing each point j > i to base point i finds all possible slopes through i.

Line:

for j in range(i + 1, n):

💡 Inner loop iterates through points after i to avoid duplicate pairs.

compare

Calculate dx, dy for points i=0 and j=1

Compute differences dx = 2 - 1 = 1 and dy = 2 - 1 = 1 between points [1,1] and [2,2].

💡 dx and dy represent the vector between two points, used to find the slope.

Line:

dx = points[j][0] - points[i][0]
dy = points[j][1] - points[i][1]

💡 Slope depends on the ratio dy/dx, so these differences are the basis for slope calculation.

compare

Check for Duplicate Points i=0 and j=1

Since dx and dy are not both zero, points are not duplicates; continue slope calculation.

💡 Duplicates are points with identical coordinates, counted separately to handle overlapping points.

Line:

if dx == 0 and dy == 0:
    duplicates += 1
    continue

💡 Duplicates affect the count of points on the same line but are rare in this example.

compare

Calculate gcd and Reduce Slope for i=0, j=1

Calculate gcd(1,1) = 1 and reduce dy and dx by dividing by gcd, slope becomes (1,1).

💡 Reducing slope to simplest integer form ensures consistent slope representation for counting.

Line:

gcd = math.gcd(dy, dx)
if gcd != 0:
    dy //= gcd
    dx //= gcd

💡 Slope normalization avoids counting the same slope multiple times with different representations.

compare

Normalize Slope Direction for i=0, j=1

Since dx is positive, slope remains (1,1) without sign change.

💡 Ensuring dx is non-negative standardizes slope direction for consistent hashmap keys.

Line:

if dx < 0:
    dx = -dx
    dy = -dy

💡 Consistent slope representation is critical for correct counting.

insert

Record Slope Count for i=0, j=1

Increment count of slope (1,1) in hashmap to 1, representing one point on this slope from base i.

💡 Counting slopes helps find how many points align on the same line through i.

Line:

slopes[(dy, dx)] += 1

💡 Slope hashmap accumulates counts for each unique slope from base point i.

traverse

Move Inner Pointer j to 2

Pointer j moves to the third point [3,3] to calculate slope with base point [1,1].

💡 Continuing to compare all points after i to find all slopes.

Line:

for j in range(i + 1, n):

💡 Each point j > i is checked to find all lines through i.

compare

Calculate dx, dy for points i=0 and j=2

Compute differences dx = 3 - 1 = 2 and dy = 3 - 1 = 2 between points [1,1] and [3,3].

💡 These differences form the vector used to calculate the slope.

Line:

dx = points[j][0] - points[i][0]
dy = points[j][1] - points[i][1]

💡 Slope depends on these differences to identify collinearity.

compare

Check for Duplicate Points i=0 and j=2

dx and dy are not zero, so points are distinct; continue slope calculation.

💡 Duplicates would increase count but are not present here.

Line:

if dx == 0 and dy == 0:
    duplicates += 1
    continue

💡 Duplicates are rare but must be handled for correctness.

compare

Calculate gcd and Reduce Slope for i=0, j=2

Calculate gcd(2,2) = 2 and reduce dy and dx by dividing by gcd, slope becomes (1,1).

💡 Reducing slope ensures all points on the same line share the same slope key.

Line:

gcd = math.gcd(dy, dx)
if gcd != 0:
    dy //= gcd
    dx //= gcd

💡 Slope normalization groups points correctly by line.

compare

Normalize Slope Direction for i=0, j=2

dx is positive, so slope remains (1,1) without sign change.

💡 Consistent slope direction is necessary for correct hashmap keys.

Line:

if dx < 0:
    dx = -dx
    dy = -dy

💡 Slope representation is consistent across all points.

insert

Record Slope Count for i=0, j=2

Increment count of slope (1,1) in hashmap to 2, indicating two points on this slope from base i.

💡 Counting multiple points on the same slope shows how many points align on a line.

Line:

slopes[(dy, dx)] += 1

💡 Slope count now reflects all points collinear with base point i.

expand

Calculate Current Max Points for i=0

Find max slope count 2, add duplicates 0 and base point 1, total 3 points on the line.

💡 This step finds the maximum points on a line through the current base point.

Line:

current_max = max(slopes.values(), default=0) + duplicates + 1

💡 The maximum count includes base point and duplicates, representing total collinear points.

expand

Update max_points with Current Max

Update global max_points from 1 to 3 because 3 points lie on the same line through i=0.

💡 Tracking the global maximum ensures the final answer is correct.

Line:

max_points = max(max_points, current_max)

💡 max_points reflects the best line found so far.

prune

Check Early Termination for i=1

At i=1, check if max_points (3) >= n - i (3 - 1 = 2) or max_points > n//2 (3 > 1). Condition true, break loop early.

💡 Early termination stops unnecessary iterations once max_points cannot be improved.

Line:

if max_points >= n - i or max_points > n // 2:
    break

💡 Early termination improves efficiency without affecting correctness.

reconstruct

Return Final Result

Return max_points = 3 as the maximum number of points on a single line.

💡 The final answer represents the largest collinear set of points found.

Line:

return max_points

💡 The algorithm successfully identified all points lie on the same line.

from collections import defaultdict
import math

def maxPoints(points):
    n = len(points)  # STEP 1
    if n <= 2:  # STEP 1
        return n
    max_points = 1  # STEP 1
    points.sort()  # STEP 1
    for i in range(n):  # STEP 2
        if max_points >= n - i or max_points > n // 2:  # STEP 3
            break
        slopes = defaultdict(int)  # STEP 4
        duplicates = 0  # STEP 4
        for j in range(i + 1, n):  # STEP 5, 11
            dx = points[j][0] - points[i][0]  # STEP 6, 12
            dy = points[j][1] - points[i][1]  # STEP 6, 12
            if dx == 0 and dy == 0:  # STEP 7, 13
                duplicates += 1
                continue
            gcd = math.gcd(dy, dx)  # STEP 8, 14
            if gcd != 0:
                dy //= gcd
                dx //= gcd
            if dx < 0:  # STEP 9, 15
                dx = -dx
                dy = -dy
            slopes[(dy, dx)] += 1  # STEP 10, 16
        current_max = max(slopes.values(), default=0) + duplicates + 1  # STEP 17
        max_points = max(max_points, current_max)  # STEP 18
    return max_points  # STEP 20

points = [[1,1],[2,2],[3,3]]
print(maxPoints(points))  # Output: 3

📊

Max Points on a Line - Watch the Algorithm Execute, Step by Step

Watching each pointer move and slope calculation helps you understand how the algorithm efficiently finds the line with the most points without checking every pair explicitly.

setup

[1,1]

0

[2,2]

1

[3,3]

2

Result: 1

traverse

i

[1,1]

0

[2,2]

1

[3,3]

2

Result: 1

prune

i

[1,1]

0

[2,2]

1

[3,3]

2

Result: 1

setup

i

[1,1]

0

[2,2]

1

[3,3]

2

Result: 1

traverse

i

[1,1]

0

j

[2,2]

1

[3,3]

2

Result: 1

compare

i

[1,1]

0

j

[2,2]

1

[3,3]

2

Result: 1

compare

i

[1,1]

0

j

[2,2]

1

[3,3]

2

Result: 1

compare

i

[1,1]

0

j

[2,2]

1

[3,3]

2

Result: 1

compare

i

[1,1]

0

j

[2,2]

1

[3,3]

2

Result: 1

insert

i

[1,1]

0

j

[2,2]

1

[3,3]

2

Result: 1

traverse

i

[1,1]

0

[2,2]

1

j

[3,3]

2

Result: 1

compare

i

[1,1]

0

[2,2]

1

j

[3,3]

2

Result: 1

compare

i

[1,1]

0

[2,2]

1

j

[3,3]

2

Result: 1

compare

i

[1,1]

0

[2,2]

1

j

[3,3]

2

Result: 1

compare

i

[1,1]

0

[2,2]

1

j

[3,3]

2

Result: 1

insert

i

[1,1]

0

[2,2]

1

j

[3,3]

2

Result: 1

expand

i

[1,1]

0

[2,2]

1

[3,3]

2

Result: 3

expand

i

[1,1]

0

[2,2]

1

[3,3]

2

Result: 3

prune

[1,1]

0

i

[2,2]

1

[3,3]

2

Result: 3

reconstruct

[1,1]

0

[2,2]

1

[3,3]

2

Result: 3

Key Takeaways

✓ Reducing slopes to their simplest integer form ensures all points on the same line share the same slope key.

Without slope normalization, the same line could be counted multiple times with different slope representations.

✓ Early termination conditions optimize the algorithm by stopping when no better solution is possible.

This optimization is subtle and can be missed by reading code but is clear when watching pointer positions and max_points updates.

✓ Counting duplicates separately is essential to handle overlapping points correctly.

Duplicates increase the count of points on a line but do not affect slope calculations, a nuance visible in the trace.

Practice

1. Given the following code for finding the minimum area rectangle, what is the returned value when the input points are [[1,1],[1,3],[3,1],[3,3],[2,2]]?

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    n = len(points)
    for i in range(n):
        for j in range(i+1, n):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if x1 != x2 and y1 != y2:
                if (x1, y2) in point_set and (x2, y1) in point_set:
                    area = abs(x1 - x2) * abs(y1 - y2)
                    if area < min_area:
                        min_area = area
    return 0 if min_area == float('inf') else min_area

points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
print(minAreaRect(points))

easy

A. 0

B. 2

C. 6

D. 4

Solution

1. Step 1: Identify rectangles formed by points

   Points (1,1), (1,3), (3,1), and (3,3) form a rectangle with area |3-1|*|3-1|=4.

2. Step 2: Check if smaller rectangles exist

   Point (2,2) does not form a smaller rectangle with any other points. So minimum area is 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Rectangle area 4 found -> output 4 [OK]

Hint: Check all diagonal pairs for rectangles [OK]

Common Mistakes:

• Returning 0 if no rectangle found
• Confusing area calculation with point count

2. 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

3. Identify the bug in the following code snippet that calculates the angle between clock hands:

class ClockAngle:
    def __init__(self):
        self.precomputed = [[0]*60 for _ in range(12)]
        for h in range(12):
            for m in range(60):
                hour_angle = h * 30  # Bug here
                minute_angle = m * 6
                diff = abs(hour_angle - minute_angle)
                self.precomputed[h][m] = min(diff, 360 - diff)

    def angleClock(self, hour: int, minutes: int) -> float:
        return self.precomputed[hour % 12][minutes]

medium

A. Line calculating hour_angle ignores minute progress, should be h * 30 + m * 0.5

B. Line calculating minute_angle should use (m % 60) * 6 to handle invalid minutes

C. Line computing diff should use (hour_angle + minute_angle) instead of abs difference

D. Line returning precomputed angle should use hour instead of hour % 12

Solution

1. Step 1: Analyze hour_angle calculation

   Hour hand moves 30 degrees per hour plus 0.5 degrees per minute. Ignoring minutes causes incorrect angles at times like 3:30.

2. Step 2: Verify other lines

   Minute angle calculation is correct, diff uses absolute difference properly, and hour modulo 12 is correct for indexing.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing minute contribution in hour_angle -> wrong angle [OK]

Hint: Hour hand moves continuously with minutes, not just discrete hours [OK]

Common Mistakes:

• Ignoring minute progress in hour hand angle
• Not normalizing hour to 12-hour format

4. What is the time complexity of the optimal single-pass Roman to Integer conversion algorithm, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because each character is compared with all others

B. O(n) because each character is processed once with constant-time operations

C. O(n log n) due to sorting or searching steps

D. O(n) but with O(n) auxiliary space for storing intermediate results

Solution

1. Step 1: Identify the loops and operations

   The algorithm iterates over the input string once, performing constant-time comparisons and arithmetic per character.

2. Step 2: Address common misconceptions

   Some candidates mistakenly think the complexity is O(n^2) by assuming nested loops or repeated lookups, but no nested iteration occurs; no sorting or extra data structures are used.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Actual complexity is O(n), but candidates often incorrectly assume O(n^2) [Trap]

Hint: Single loop with constant work per char -> O(n) [OK]

Common Mistakes:

• Assuming nested loops
• Confusing auxiliary space with time
• Thinking sorting is involved

5. Suppose the clock can show times with fractional minutes (e.g., 3:30.5). Which modification to the precomputation approach is necessary to handle queries with fractional minutes correctly?

hard

A. Increase precomputed table size to include fractional minute indices (e.g., 60 * 10 for tenths of minutes).

B. Precompute only hour angles and calculate minute angles on the fly for fractional minutes.

C. Round fractional minutes down to nearest integer and use existing precomputed table.

D. Use the brute force direct calculation formula at query time instead of precomputation.

Solution

1. Step 1: Understand fractional minute impact

   Precomputing all fractional minute values is infeasible due to infinite possibilities.

2. Step 2: Evaluate options

   Increasing table size exponentially is impractical; rounding loses precision; precomputing only hour angles is insufficient because minute angle varies continuously.

3. Step 3: Use direct calculation

   Calculating angles on the fly with the formula handles fractional minutes accurately and efficiently.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Direct formula supports fractional inputs without huge memory [OK]

Hint: Precompute only works for discrete inputs; fractional requires formula [OK]

Common Mistakes:

• Trying to precompute infinite fractional values
• Rounding fractional minutes losing accuracy