Max Points on a Line - Practice Coding Problems

Max Points on a Line - Problem

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Two points always define a line, but three or more points are collinear if they all lie on the same line. The challenge is to efficiently find the largest group of collinear points.

Note: Handle edge cases like duplicate points, vertical lines, and horizontal lines carefully.

Input & Output

Example 1 — Three Collinear Points

$ Input: points = [[1,1],[2,2],[3,3]]

› Output: 3

💡 Note: All three points lie on the line y = x, so the maximum is 3 collinear points

Example 2 — Mixed Points

$ Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

› Output: 4

💡 Note: Points (1,1), (3,2), (5,3) lie on line y = 0.5x + 0.5, but actually (1,1),(2,3),(1,4),(4,1) might form a better line depending on calculation

Example 3 — Duplicate Points

$ Input: points = [[1,1],[1,1],[2,2]]

› Output: 3

💡 Note: Two duplicate points at (1,1) plus point (2,2) - all three can be considered on the same line

Constraints

1 ≤ points.length ≤ 300
points[i].length == 2
-10⁴ ≤ x_i, y_i ≤ 10⁴
All the points are unique except possibly some duplicates

Visualization

Tap to expand

Understanding the Visualization

Input Points

Given array of coordinate points on 2D plane

Find Collinear

Points with same slope from anchor are on same line

Count Maximum

Return the largest group of collinear points found

Key Takeaway

🎯 Key Insight: Points are collinear if they have identical slopes relative to any fixed anchor point

Asked in

G Google 15 🍎 Apple 12 M Microsoft 10 a Amazon 8

The key insight is that points are collinear if they have the same slope relative to a fixed anchor point. Best approach uses slope counting with hash maps for each anchor point. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Slope Counting	O(n²)	O(n)	For each point, count how many points share the same slope
Brute Force	O(n⁴)	O(1)	Check every combination of three points to see if they're collinear

Slope Counting — Algorithm Steps

Step 1: For each point as anchor, create slope frequency map
Step 2: Calculate slope to every other point using reduced fractions
Step 3: Handle special cases: vertical lines, duplicates, horizontal lines
Step 4: Track maximum count found for any slope

Visualization

Tap to expand

Step-by-Step Walkthrough

Fix Anchor

Choose one point as anchor, calculate slopes to all others

Count Slopes

Use hash map to count how many points share each slope

Find Maximum

The slope with highest count gives max collinear points

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_POINTS 300
#define MAX_SLOPES 1000

typedef struct {
    char slope[50];
    int count;
} SlopeEntry;

int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int solution(int** points, int n) {
    if (n <= 2) return n;
    
    int maxPoints = 2;
    
    for (int i = 0; i < n; i++) {
        SlopeEntry slopes[MAX_SLOPES];
        int slopeCount = 0;
        int duplicate = 0;
        int vertical = 0;
        int localMax = 0;
        
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            
            int dx = points[j][0] - points[i][0];
            int dy = points[j][1] - points[i][1];
            
            if (dx == 0 && dy == 0) {
                // Duplicate points
                duplicate++;
                continue;
            } else if (dx == 0) {
                // Vertical line
                vertical++;
                if (vertical > localMax) localMax = vertical;
            } else {
                // Calculate slope as reduced fraction
                int g = gcd(dx, dy);
                char slope[50];
                sprintf(slope, "%d/%d", dy/g, dx/g);
                
                // Find or create slope entry
                int found = 0;
                for (int k = 0; k < slopeCount; k++) {
                    if (strcmp(slopes[k].slope, slope) == 0) {
                        slopes[k].count++;
                        if (slopes[k].count > localMax) localMax = slopes[k].count;
                        found = 1;
                        break;
                    }
                }
                if (!found && slopeCount < MAX_SLOPES) {
                    strcpy(slopes[slopeCount].slope, slope);
                    slopes[slopeCount].count = 1;
                    if (1 > localMax) localMax = 1;
                    slopeCount++;
                }
            }
        }
        
        if (localMax + duplicate + 1 > maxPoints) {
            maxPoints = localMax + duplicate + 1; // +1 for anchor point
        }
    }
    
    return maxPoints;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[x1,y1],[x2,y2],...]
    int** points = malloc(MAX_POINTS * sizeof(int*));
    int n = 0;
    
    char* ptr = strchr(line, '[');
    while (ptr && (ptr = strchr(ptr + 1, '['))) {
        points[n] = malloc(2 * sizeof(int));
        sscanf(ptr, "[%d,%d]", &points[n][0], &points[n][1]);
        n++;
        ptr = strchr(ptr, ']');
    }
    
    int result = solution(points, n);
    printf("%d\n", result);
    
    for (int i = 0; i < n; i++) free(points[i]);
    free(points);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops: outer fixes anchor point, inner calculates slopes to all others

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map stores slope frequencies, maximum n-1 unique slopes per anchor

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~35 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Slope Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler