Max Points on a Line

🎯

Max Points on a Line

hardMATHAmazonGoogleFacebook

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

💡 This problem involves understanding how to represent lines mathematically and efficiently count points that share the same line. Beginners often struggle with handling edge cases like vertical lines and overlapping points, and with representing slopes precisely to avoid floating-point errors.

📋

Problem Statement

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

💡

Example

Input"[[1,1],[2,2],[3,3]]"

Output3

All three points lie on the line y = x.

Input"[[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]"

Output4

The points [1,1], [3,2], [5,3], and [1,4] lie on the same line.

• All points are identical → output is n
• All points are vertical line → output is n
• Points with negative coordinates → should handle slope sign correctly
• Points with zero slope (horizontal line) → should count correctly

⚠️

Common Mistakes

Using floating-point slopes directly

Precision errors cause incorrect grouping of points on the same line

✅ Use gcd to reduce slope to a fraction represented by integer pairs

Not handling duplicate points

Under-counting points on the same line, leading to wrong answers

✅ Count duplicates separately and add them to the max count

Ignoring vertical lines (dx=0)

Division by zero or missing vertical lines in slope calculation

✅ Handle vertical lines as a special case with a unique slope key

Not normalizing slope sign

Slopes like (1, -1) and (-1, 1) treated as different lines incorrectly

✅ Normalize slope so dx is always positive, adjusting dy accordingly

Not using early termination in large inputs

Solution times out on large test cases

✅ Add early break conditions when max points found cannot be beaten

🧠

Brute Force (Nested Loops Checking Every Pair)

💡 This approach exists to build intuition by checking every pair of points and counting how many points align with that pair. It is simple but inefficient, helping beginners understand the problem's geometric nature.

Intuition

For each point, check the line formed with every other point and count how many points lie on that line. The maximum count found is the answer.

Algorithm

1. Initialize max_points to 1 (at least one point exists).
2. For each point i, iterate over every other point j > i.
3. Calculate the slope between points i and j, handling vertical lines separately.
4. Count how many points k lie on the line defined by i and j by comparing slopes.
5. Update max_points if a larger count is found.

💡 The nested loops and slope calculations can be tricky to visualize, especially handling vertical lines and duplicates, but this method directly tests the definition of points on a line.

</>

Code

from collections import defaultdict

def maxPoints(points):
    if len(points) <= 2:
        return len(points)
    max_points = 1
    n = len(points)
    for i in range(n):
        slopes = defaultdict(int)
        duplicates = 0
        for j in range(i + 1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            if dx == 0 and dy == 0:
                duplicates += 1
                continue
            if dx == 0:
                slope = 'inf'
            else:
                slope = dy / dx
            slopes[slope] += 1
        current_max = max(slopes.values(), default=0) + duplicates + 1
        max_points = max(max_points, current_max)
    return max_points

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

Line Notes

if len(points) <= 2:Handle trivial cases where all points are on the same line by default

for i in range(n):Outer loop picks each point as a base to compare slopes

if dx == 0 and dy == 0:Count duplicates of the same point to add later

slope = dy / dxCalculate slope; float division is simple but can cause precision issues

import java.util.*;

public class MaxPointsOnLine {
    public static int maxPoints(int[][] points) {
        if (points.length <= 2) return points.length;
        int maxPoints = 1;
        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> slopes = new HashMap<>();
            int duplicates = 0;
            for (int j = i + 1; j < points.length; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                if (dx == 0 && dy == 0) {
                    duplicates++;
                    continue;
                }
                String slope;
                if (dx == 0) slope = "inf";
                else slope = String.valueOf((double) dy / dx);
                slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);
            }
            int currentMax = slopes.values().stream().max(Integer::compare).orElse(0) + duplicates + 1;
            maxPoints = Math.max(maxPoints, currentMax);
        }
        return maxPoints;
    }

    public static void main(String[] args) {
        int[][] points = {{1,1},{2,2},{3,3}};
        System.out.println(maxPoints(points)); // Output: 3
    }
}

Line Notes

if (points.length <= 2) return points.length;Quickly handle trivial cases with 2 or fewer points

for (int i = 0; i < points.length; i++) {Outer loop selects base point for slope calculation

if (dx == 0 && dy == 0) {Detect duplicate points to count separately

slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);Count how many points share the same slope with base point

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;

int maxPoints(vector<vector<int>>& points) {
    if (points.size() <= 2) return points.size();
    int max_points = 1;
    for (int i = 0; i < points.size(); i++) {
        unordered_map<string, int> slopes;
        int duplicates = 0;
        for (int j = i + 1; j < points.size(); j++) {
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
            if (dx == 0 && dy == 0) {
                duplicates++;
                continue;
            }
            string slope;
            if (dx == 0) slope = "inf";
            else slope = to_string((double)dy / dx);
            slopes[slope]++;
        }
        int current_max = 0;
        for (auto& p : slopes) current_max = max(current_max, p.second);
        max_points = max(max_points, current_max + duplicates + 1);
    }
    return max_points;
}

int main() {
    vector<vector<int>> points = {{1,1},{2,2},{3,3}};
    cout << maxPoints(points) << endl; // Output: 3
    return 0;
}

Line Notes

if (points.size() <= 2) return points.size();Handle trivial cases quickly

for (int i = 0; i < points.size(); i++) {Outer loop picks base point

if (dx == 0 && dy == 0) {Count duplicates separately to add later

slopes[slope]++;Increment count of points sharing the same slope

function maxPoints(points) {
    if (points.length <= 2) return points.length;
    let maxPoints = 1;
    for (let i = 0; i < points.length; i++) {
        const slopes = new Map();
        let duplicates = 0;
        for (let j = i + 1; j < points.length; j++) {
            const dx = points[j][0] - points[i][0];
            const dy = points[j][1] - points[i][1];
            if (dx === 0 && dy === 0) {
                duplicates++;
                continue;
            }
            let slope;
            if (dx === 0) slope = 'inf';
            else slope = dy / dx;
            slopes.set(slope, (slopes.get(slope) || 0) + 1);
        }
        let currentMax = 0;
        for (const count of slopes.values()) {
            if (count > currentMax) currentMax = count;
        }
        maxPoints = Math.max(maxPoints, currentMax + duplicates + 1);
    }
    return maxPoints;
}

// Test
console.log(maxPoints([[1,1],[2,2],[3,3]])); // Output: 3

Line Notes

if (points.length <= 2) return points.length;Handle trivial cases with few points

for (let i = 0; i < points.length; i++) {Outer loop selects base point

if (dx === 0 && dy === 0) {Count duplicates to add later

slopes.set(slope, (slopes.get(slope) || 0) + 1);Track count of points with same slope

⏱

Complexity

TimeO(n^2)

SpaceO(n)

For each point, we check slopes with every other point, resulting in n*(n-1)/2 pairs. The hashmap stores slopes per base point, using O(n) space.

💡 For n=20, this means about 190 pairs checked, which is manageable, but for n=10^5 it becomes too slow.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but is essential to understand the problem and build towards optimized solutions.

🧠

Better Approach Using Reduced Fraction Slopes and Hash Map

💡 This approach improves on brute force by representing slopes as reduced fractions to avoid floating-point precision errors and uses a hashmap per point to count points on the same line efficiently.

Intuition

Instead of using floating-point slopes, represent slopes as pairs of integers reduced by their gcd. This ensures identical slopes are counted correctly. For each point, count how many points share the same reduced slope.

Algorithm

1. For each point i, initialize a hashmap to count slopes as reduced fractions.
2. For each other point j, compute dx and dy, then reduce by gcd to get normalized slope.
3. Handle vertical lines by setting dx=0 and horizontal lines by dy=0 appropriately.
4. Count duplicates separately.
5. Update max points with the maximum count of points sharing the same slope plus duplicates plus the base point.

💡 Reducing slopes to fractions avoids floating-point errors and ensures correct grouping of points on the same line.

</>

Code

from collections import defaultdict
import math

def maxPoints(points):
    if len(points) <= 2:
        return len(points)
    max_points = 1
    n = len(points)
    for i in range(n):
        slopes = defaultdict(int)
        duplicates = 0
        for j in range(i + 1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            if dx == 0 and dy == 0:
                duplicates += 1
                continue
            gcd = math.gcd(dy, dx)
            if gcd != 0:
                dy //= gcd
                dx //= gcd
            # Handle sign to keep dx positive for uniqueness
            if dx < 0:
                dx = -dx
                dy = -dy
            slopes[(dy, dx)] += 1
        current_max = max(slopes.values(), default=0) + duplicates + 1
        max_points = max(max_points, current_max)
    return max_points

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

Line Notes

import mathImport gcd function to reduce fractions

gcd = math.gcd(dy, dx)Compute gcd to reduce slope fraction

if dx < 0:Normalize slope so dx is always positive for consistent keys

slopes[(dy, dx)] += 1Use tuple of reduced dy and dx as hashmap key to count points

import java.util.*;

public class MaxPointsOnLine {
    private static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static int maxPoints(int[][] points) {
        if (points.length <= 2) return points.length;
        int maxPoints = 1;
        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> slopes = new HashMap<>();
            int duplicates = 0;
            for (int j = i + 1; j < points.length; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                if (dx == 0 && dy == 0) {
                    duplicates++;
                    continue;
                }
                int gcd = gcd(dy, dx);
                if (gcd != 0) {
                    dy /= gcd;
                    dx /= gcd;
                }
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                }
                String slope = dy + "," + dx;
                slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);
            }
            int currentMax = slopes.values().stream().max(Integer::compare).orElse(0) + duplicates + 1;
            maxPoints = Math.max(maxPoints, currentMax);
        }
        return maxPoints;
    }

    public static void main(String[] args) {
        int[][] points = {{1,1},{2,2},{3,3}};
        System.out.println(maxPoints(points)); // Output: 3
    }
}

Line Notes

private static int gcd(int a, int b)Helper function to compute gcd for fraction reduction

if (gcd != 0)Reduce dy and dx by gcd to normalize slope

if (dx < 0)Normalize slope sign to keep dx positive for consistent hashmap keys

String slope = dy + "," + dx;Create string key representing reduced slope fraction

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int maxPoints(vector<vector<int>>& points) {
    if (points.size() <= 2) return points.size();
    int max_points = 1;
    for (int i = 0; i < points.size(); i++) {
        unordered_map<string, int> slopes;
        int duplicates = 0;
        for (int j = i + 1; j < points.size(); j++) {
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
            if (dx == 0 && dy == 0) {
                duplicates++;
                continue;
            }
            int g = gcd(dy, dx);
            if (g != 0) {
                dy /= g;
                dx /= g;
            }
            if (dx < 0) {
                dx = -dx;
                dy = -dy;
            }
            string slope = to_string(dy) + "," + to_string(dx);
            slopes[slope]++;
        }
        int current_max = 0;
        for (auto& p : slopes) current_max = max(current_max, p.second);
        max_points = max(max_points, current_max + duplicates + 1);
    }
    return max_points;
}

int main() {
    vector<vector<int>> points = {{1,1},{2,2},{3,3}};
    cout << maxPoints(points) << endl; // Output: 3
    return 0;
}

Line Notes

int gcd(int a, int b)Recursive gcd function to reduce slope fractions

if (g != 0)Reduce dy and dx by gcd for normalization

if (dx < 0)Normalize slope sign for consistent hashmap keys

string slope = to_string(dy) + "," + to_string(dx);Create unique string key for slope

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

function maxPoints(points) {
    if (points.length <= 2) return points.length;
    let maxPoints = 1;
    for (let i = 0; i < points.length; i++) {
        const slopes = new Map();
        let duplicates = 0;
        for (let j = i + 1; j < points.length; j++) {
            let dx = points[j][0] - points[i][0];
            let dy = points[j][1] - points[i][1];
            if (dx === 0 && dy === 0) {
                duplicates++;
                continue;
            }
            let g = gcd(dy, dx);
            if (g !== 0) {
                dy /= g;
                dx /= g;
            }
            if (dx < 0) {
                dx = -dx;
                dy = -dy;
            }
            const slope = dy + ',' + dx;
            slopes.set(slope, (slopes.get(slope) || 0) + 1);
        }
        let currentMax = 0;
        for (const count of slopes.values()) {
            if (count > currentMax) currentMax = count;
        }
        maxPoints = Math.max(maxPoints, currentMax + duplicates + 1);
    }
    return maxPoints;
}

// Test
console.log(maxPoints([[1,1],[2,2],[3,3]])); // Output: 3

Line Notes

function gcd(a, b)Recursive gcd function to reduce fractions

if (g !== 0)Reduce dy and dx by gcd for slope normalization

if (dx < 0)Normalize slope sign for consistent keys

slopes.set(slope, (slopes.get(slope) || 0) + 1);Count points sharing the same reduced slope

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Still O(n^2) due to nested loops, but slope calculation is more precise and consistent. Space is O(n) for hashmap per base point.

💡 For n=20, this is about 190 pairs, but the improved slope representation avoids errors and is interview-worthy.

Interview Verdict: Accepted / Practical for interviews

This approach is efficient enough for typical interview constraints and avoids floating-point pitfalls.

🧠

Optimal Approach with Early Termination and Integer Slope Representation

💡 This approach adds early termination to reduce unnecessary computations and uses integer slope representation with gcd normalization, making it optimal for large inputs.

Intuition

By sorting points or breaking early when the remaining points cannot beat the current max, we reduce runtime. Using integer slopes avoids floating-point errors and ensures correctness.

Algorithm

1. Initialize max_points to 1.
2. For each point i, if max_points >= n - i or max_points > n/2, break early as no better line is possible.
3. For each other point j > i, compute reduced slope as integer pair using gcd.
4. Count duplicates and slopes in a hashmap.
5. Update max_points with the maximum count found plus duplicates plus 1.

💡 Early termination reduces runtime by skipping points that cannot improve the max. Integer slope representation ensures correctness.

</>

Code

from collections import defaultdict
import math

def maxPoints(points):
    n = len(points)
    if n <= 2:
        return n
    max_points = 1
    points.sort()  # Sort to enable early termination
    for i in range(n):
        if max_points >= n - i or max_points > n // 2:
            break
        slopes = defaultdict(int)
        duplicates = 0
        for j in range(i + 1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            if dx == 0 and dy == 0:
                duplicates += 1
                continue
            gcd = math.gcd(dy, dx)
            if gcd != 0:
                dy //= gcd
                dx //= gcd
            if dx < 0:
                dx = -dx
                dy = -dy
            slopes[(dy, dx)] += 1
        current_max = max(slopes.values(), default=0) + duplicates + 1
        max_points = max(max_points, current_max)
    return max_points

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

Line Notes

points.sort()Sort points to enable early termination optimization

if max_points >= n - i or max_points > n // 2:Early break if no better line can be found

gcd = math.gcd(dy, dx)Reduce slope fraction to normalized form

slopes[(dy, dx)] += 1Count points sharing the same slope with base point

import java.util.*;

public class MaxPointsOnLine {
    private static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        Arrays.sort(points, Comparator.comparingInt(a -> a[0]));
        int maxPoints = 1;
        for (int i = 0; i < n; i++) {
            if (maxPoints >= n - i || maxPoints > n / 2) break;
            Map<String, Integer> slopes = new HashMap<>();
            int duplicates = 0;
            for (int j = i + 1; j < n; j++) {
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];
                if (dx == 0 && dy == 0) {
                    duplicates++;
                    continue;
                }
                int gcd = gcd(dy, dx);
                if (gcd != 0) {
                    dy /= gcd;
                    dx /= gcd;
                }
                if (dx < 0) {
                    dx = -dx;
                    dy = -dy;
                }
                String slope = dy + "," + dx;
                slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);
            }
            int currentMax = slopes.values().stream().max(Integer::compare).orElse(0) + duplicates + 1;
            maxPoints = Math.max(maxPoints, currentMax);
        }
        return maxPoints;
    }

    public static void main(String[] args) {
        int[][] points = {{1,1},{2,2},{3,3}};
        System.out.println(maxPoints(points)); // Output: 3
    }
}

Line Notes

Arrays.sort(points, Comparator.comparingInt(a -> a[0]));Sort points by x-coordinate for early termination

if (maxPoints >= n - i || maxPoints > n / 2) break;Stop early if no better line can be found

int gcd = gcd(dy, dx);Reduce slope fraction to normalized form

slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);Count points sharing the same slope

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int maxPoints(vector<vector<int>>& points) {
    int n = points.size();
    if (n <= 2) return n;
    sort(points.begin(), points.end());
    int max_points = 1;
    for (int i = 0; i < n; i++) {
        if (max_points >= n - i || max_points > n / 2) break;
        unordered_map<string, int> slopes;
        int duplicates = 0;
        for (int j = i + 1; j < n; j++) {
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
            if (dx == 0 && dy == 0) {
                duplicates++;
                continue;
            }
            int g = gcd(dy, dx);
            if (g != 0) {
                dy /= g;
                dx /= g;
            }
            if (dx < 0) {
                dx = -dx;
                dy = -dy;
            }
            string slope = to_string(dy) + "," + to_string(dx);
            slopes[slope]++;
        }
        int current_max = 0;
        for (auto& p : slopes) current_max = max(current_max, p.second);
        max_points = max(max_points, current_max + duplicates + 1);
    }
    return max_points;
}

int main() {
    vector<vector<int>> points = {{1,1},{2,2},{3,3}};
    cout << maxPoints(points) << endl; // Output: 3
    return 0;
}

Line Notes

sort(points.begin(), points.end());Sort points to enable early termination optimization

if (max_points >= n - i || max_points > n / 2) break;Early break to reduce unnecessary computations

int g = gcd(dy, dx);Reduce slope fraction to normalized form

slopes[slope]++;Count points sharing the same slope

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

function maxPoints(points) {
    const n = points.length;
    if (n <= 2) return n;
    points.sort((a, b) => a[0] - b[0]);
    let maxPoints = 1;
    for (let i = 0; i < n; i++) {
        if (maxPoints >= n - i || maxPoints > n / 2) break;
        const slopes = new Map();
        let duplicates = 0;
        for (let j = i + 1; j < n; j++) {
            let dx = points[j][0] - points[i][0];
            let dy = points[j][1] - points[i][1];
            if (dx === 0 && dy === 0) {
                duplicates++;
                continue;
            }
            let g = gcd(dy, dx);
            if (g !== 0) {
                dy /= g;
                dx /= g;
            }
            if (dx < 0) {
                dx = -dx;
                dy = -dy;
            }
            const slope = dy + ',' + dx;
            slopes.set(slope, (slopes.get(slope) || 0) + 1);
        }
        let currentMax = 0;
        for (const count of slopes.values()) {
            if (count > currentMax) currentMax = count;
        }
        maxPoints = Math.max(maxPoints, currentMax + duplicates + 1);
    }
    return maxPoints;
}

// Test
console.log(maxPoints([[1,1],[2,2],[3,3]])); // Output: 3

Line Notes

points.sort((a, b) => a[0] - b[0]);Sort points by x-coordinate for early termination

if (maxPoints >= n - i || maxPoints > n / 2) break;Stop early if no better line can be found

let g = gcd(dy, dx);Reduce slope fraction to normalized form

slopes.set(slope, (slopes.get(slope) || 0) + 1);Count points sharing the same slope

⏱

Complexity

TimeO(n^2) with early termination

SpaceO(n)

Early termination reduces average runtime by skipping unnecessary checks. Still worst-case O(n^2) but faster in practice.

💡 For large n, early breaks can save significant time, making this approach practical for interviews.

Interview Verdict: Accepted / Optimal for interviews

This is the best practical approach combining correctness, efficiency, and code clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the second or third approach in 95% of interviews for correctness and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Reduced Fraction Slopes with Hash Map	O(n^2)	O(n)	No	N/A	Code this approach for correctness and precision
3. Optimal with Early Termination	O(n^2) average with pruning	O(n)	No	N/A	Code this approach if time permits for best performance

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints, including duplicates and vertical lines.Start with the brute force approach to show understanding of the problem.Explain the issues with floating-point slopes and introduce reduced fraction slopes.Present the optimal approach with early termination for efficiency.Write clean code and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of geometry, handling edge cases, precision issues, and ability to optimize nested loops.

Common Follow-ups

• How to handle very large inputs efficiently → use early termination and pruning
• How to avoid floating-point precision errors → use gcd to reduce slopes to fractions

💡 These follow-ups test your ability to optimize and handle tricky numerical issues common in geometry problems.

🔍

Pattern Recognition

When to Use

1) Given points on a plane, 2) Asked for max collinear points, 3) Need to handle duplicates and vertical lines, 4) Precision issues with slopes arise

Signature Phrases

max points on the same straight linepoints lie on the same line

NOT This Pattern When

Closest Pair of Points - focuses on distance, not collinearity

Similar Problems

Max Points on a Line II - extension with dynamic pointsCollinear Points Count - counting all sets of collinear pointsLine Through Points - finding line equations through points

Practice

1. Given the following code snippet, what is the output of clock.angleClock(3, 30)?

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 + m * 0.5
                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]

clock = ClockAngle()
print(clock.angleClock(3, 30))

easy

A. 105

B. 90

C. 75

D. 60

Solution

1. Step 1: Calculate hour hand angle at 3:30

   Hour angle = 3 * 30 + 30 * 0.5 = 90 + 15 = 105 degrees.

2. Step 2: Calculate minute hand angle and difference

   Minute angle = 30 * 6 = 180 degrees. Difference = |105 - 180| = 75 degrees. Minimal angle = 75 degrees.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Precomputed table stores minimal angle correctly -> 75 [OK]

Hint: Hour hand moves 0.5° per minute, not fixed 30° per hour [OK]

Common Mistakes:

• Using only hour * 30 without minute adjustment
• Returning absolute difference without min(., 360 - .)

2. Given the following recursive reverse integer code, what is the final output when input is 120?

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
        if rev > INT_MAX // 10 or (rev == INT_MAX // 10 and pop > 7):
            return 0
        return helper(num // 10, rev * 10 + pop)

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

print(reverse(120))

easy

A. 0

B. 21

C. 12

D. 21

Solution

1. Step 1: Trace helper calls for input 120

   helper(120,0) -> pop=0, helper(12,0*10+0=0) helper(12,0) -> pop=2, helper(1,0*10+2=2) helper(1,2) -> pop=1, helper(0,2*10+1=21) helper(0,21) returns 21

2. Step 2: Apply sign and check overflow

   Input is positive, so final return is 21. No overflow detected.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Reversed 120 is 21 after dropping trailing zero [OK]

Hint: Trailing zeros disappear after reversal [OK]

Common Mistakes:

• Returning 12 by reversing digits incorrectly
• Returning 0 due to wrong overflow check
• Confusing pop digit order

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. Suppose the Excel column titles can now include lowercase letters (a-z) in addition to uppercase (A-Z), where 'a' corresponds to 1 and 'z' to 26, independent of uppercase letters. How should the algorithm be modified to correctly convert such titles to numbers?

hard

A. Convert all letters to uppercase and use existing logic

B. Treat uppercase letters as base-26 digits and lowercase letters as separate base-26 digits, then sum

C. Use a combined mapping where 'A'-'Z' and 'a'-'z' both map to 1-26, then apply base-26 logic

D. Map uppercase and lowercase letters separately to 1-26 and multiply by 52 instead of 26

Solution

1. Step 1: Understand the new character set

   Now there are 52 possible characters (A-Z and a-z), each mapping to 1-26 independently.

2. Step 2: Adjust base and mapping accordingly

   Since there are 52 distinct characters, the base must be 52, and mapping must distinguish uppercase and lowercase letters.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base must match character set size; 26 is insufficient for mixed case [OK]

Hint: Base equals number of distinct characters [OK]

Common Mistakes:

• Ignoring case difference
• Using base 26 for 52 chars
• Mapping lowercase to same as uppercase