LeetCode 149: Max Points on a Line Solution

Master LeetCode problem 149 (Max Points on a Line), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

149. Max Points on a Line

Hard

Array Hash Table Math Geometry

Problem Explanation

Explanation

To solve this problem, we can iterate through each pair of points and calculate the slope of the line passing through them. By keeping track of the frequency of each slope in a hashmap, we can find the maximum number of points that lie on the same straight line.

For each point, consider it as the starting point.
Calculate the slope with all other points.
Keep track of the frequency of each slope.
Update the maximum number of points that lie on the same line for each starting point.
Return the overall maximum.

Time complexity: O(n^2) where n is the number of points. Space complexity: O(n)

Solution Code

import java.util.*;

class Solution {
    public int maxPoints(int[][] points) {
        if (points.length <= 2) {
            return points.length;
        }
        
        int maxPoints = 2; // At least 2 points are needed to form a line
        for (int i = 0; i < points.length; i++) {
            Map<Double, Integer> slopeMap = new HashMap<>();
            int samePoints = 0;
            int localMaxPoints = 1;
            
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                
                int x1 = points[i][0];
                int y1 = points[i][1];
                int x2 = points[j][0];
                int y2 = points[j][1];
                
                if (x1 == x2 && y1 == y2) {
                    samePoints++;
                } else {
                    double slope = (x1 == x2) ? Double.MAX_VALUE : 1.0 * (y2 - y1) / (x2 - x1);
                    slopeMap.put(slope, slopeMap.getOrDefault(slope, 1) + 1);
                    localMaxPoints = Math.max(localMaxPoints, slopeMap.get(slope));
                }
            }
            
            maxPoints = Math.max(maxPoints, localMaxPoints + samePoints);
        }
        
        return maxPoints;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 149 (Max Points on a Line)?

This page provides optimized solutions for LeetCode problem 149 (Max Points on a Line) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 149 (Max Points on a Line)?

The time complexity for LeetCode 149 (Max Points on a Line) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 149 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 149 in Java, C++, or Python.

Back to LeetCode Solutions