NUHMAN.com

Introduction

In this problem, we are given a set of points on a 2D plane, and our goal is to find the maximum number of points that lie on the same straight line.

This problem is a good exercise in geometry and hash maps. The key observation here is that points are collinear (i.e., they lie on the same line) if the slope between any two points is the same.

We can use this property and a hash map to efficiently solve the problem.

Problem Statement

Given an array of points where each point is represented by (x, y) coordinates, find the maximum number of points that lie on the same straight line.

go

type Point struct {
    X int
    Y int
}

Return the maximum number of points that lie on the same straight line.

Approach

We can use the following approach:

1. Slope Calculation: For each pair of points, calculate the slope of the line connecting them. The slope between two points (x1, y1) and (x2, y2) is given by:
2. slope=y2−y1x2−x1\text{slope} = \frac{y2 - y1}{x2 - x1}slope=x2−x1y2−y1​If the points have the same x coordinate (vertical line), the slope is undefined, so we handle it as a special case.
3. Hash Map: We store the slopes in a hash map, where the key is the slope (as a fraction), and the value is the count of points that share that slope with the current point.
4. Iterate through each point: For each point, compute the slope of the line it forms with every other point and store the results in the hash map. The maximum count in the hash map gives the maximum number of points that lie on a line for that specific point.
5. Edge Cases: Handle vertical lines, duplicate points, and points with the same coordinates.

Go Implementation

go

package main

import (
    "fmt"
    "math/gcd"
)

type Point struct {
    X int
    Y int
}

func maxPoints(points []Point) int {
    n := len(points)
    if n <= 2 {
        return n
    }

    result := 0
    for i := 0; i < n; i++ {
        slopes := make(map[string]int)
        duplicate := 1
        localMax := 0
        
        for j := 0; j < n; j++ {
            if i != j {
                dx := points[j].X - points[i].X
                dy := points[j].Y - points[i].Y
                if dx == 0 && dy == 0 {
                    duplicate++
                } else {
                    g := gcd(dx, dy) // Get the greatest common divisor to simplify the slope
                    dx /= g
                    dy /= g
                    // Handle negative slope consistently
                    if dx < 0 {
                        dx, dy = -dx, -dy
                    }
                    slope := fmt.Sprintf("%d/%d", dx, dy)
                    slopes[slope]++
                    localMax = max(localMax, slopes[slope])
                }
            }
        }
        result = max(result, localMax+duplicate)
    }
    
    return result
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Time and Space Complexity

OperationComplexityTimeO(n²)SpaceO(n)

• Time: For each point, we calculate slopes for every other point, which results in O(n²) time complexity.
• Space: We use a hash map to store slopes, which requires O(n) space in the worst case.

Example

Input:

css

points := []Point{
    {1, 1},
    {2, 2},
    {3, 3},
    {4, 1},
    {5, 3},
    {6, 4},
}

Output:

4

Explanation:

The maximum number of points that lie on the same straight line is 4 (points (1, 1), (2, 2), (3, 3), and (5, 3)).

Why This Approach Works

• Efficiency: By calculating slopes and storing them in a hash map, we avoid the O(n³) brute force approach. Instead, we achieve an O(n²) solution.
• Handling Vertical Lines: We use the greatest common divisor (gcd) to simplify slope calculation and handle vertical lines, where the slope would otherwise be undefined.
• Duplicate Points: We count duplicate points separately to ensure we don't miss any point on a line.

Conclusion

This problem is a great example of combining geometric properties with efficient data structures like hash maps to solve a complex problem in a time-efficient manner. The solution leverages slope calculation and hashing to ensure that we can handle large sets of points efficiently.