Description
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.
Examples:
Example 1:
Input: points = [[1,1],[2,2],[3,3]]
Output: 3
Example 2:
Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4Solution in Python
To solve the problem of finding the maximum number of points that lie on the same straight line, we can use the concept of slopes between points. By calculating the slope between each pair of points, we can determine how many points share the same slope, and thus lie on the same line.
Step-by-step explanation and the Python implementation of the solution:
- Handle edge cases: If the number of points is 1 or less, return the length of the points array because one point or no points trivially lie on the same line.
- Iterate through each point: For each point, calculate the slope it forms with every other point.
- Use a dictionary to count slopes: Use a dictionary to keep track of how many times each slope appears for a given point. Each unique slope represents a unique line passing through that point.
- Calculate the maximum number of points on a line: For each point, find the maximum count of points that lie on a line through it, and update the global maximum accordingly.
- Handle vertical and horizontal lines: Special care should be taken for vertical lines (where the change in x is zero) and horizontal lines.
Python
from collections import defaultdict
from math import gcd
from typing import List
class Solution:
def maxPoints(self, points: List[List[int]]) -> int:
if len(points) <= 1:
return len(points)
def get_slope(p1, p2):
dx = p2[0] - p1[0]
dy = p2[1] - p1[1]
if dx == 0: # vertical line
return ('inf', 0)
if dy == 0: # horizontal line
return (0, 'inf')
g = gcd(dx, dy)
return (dy // g, dx // g)
max_points_on_a_line = 1
for i in range(len(points)):
slopes = defaultdict(int)
for j in range(len(points)):
if i != j:
slope = get_slope(points[i], points[j])
slopes[slope] += 1
max_points_on_a_line = max(max_points_on_a_line, max(slopes.values(), default=0) + 1)
return max_points_on_a_lineDetailed Explanation:
- Edge Case: If there is only one point or no points, return the number of points since that’s the maximum that can be on a single line.
- Helper Function
get_slope:- Computes the slope between two points p1 and p2.
- Handles vertical lines by returning a tuple
('inf', 0). - Handles horizontal lines by returning a tuple
(0, 'inf'). - For other lines, computes the slope as a reduced fraction using the greatest common divisor (gcd).
- Main Logic:
- Iterate through each point, considering it as the base point.
- For each base point, compute slopes with all other points and store the frequency of each slope in a dictionary.
- Track the maximum number of points that can form a line through the base point by finding the most frequent slope and adding one (to include the base point itself).
- Update the global maximum with this value.
- Return Result: After processing all points, the global maximum contains the highest number of points on a single line.
This solution efficiently counts points on the same line using slopes, ensuring O(n2) complexity which is feasible given the constraint 1≤points.length≤300.
Solution in Javascript
JavaScript
/**
* @param {number[][]} points
* @return {number}
*/
var maxPoints = function(points) {
if (points.length <= 1) {
return points.length;
}
// Helper function to calculate the greatest common divisor (GCD)
const gcd = (a, b) => {
if (b === 0) return a;
return gcd(b, a % b);
};
// Helper function to get the slope between two points
const getSlope = (p1, p2) => {
const dx = p2[0] - p1[0];
const dy = p2[1] - p1[1];
if (dx === 0) return ['inf', 0]; // Vertical line
if (dy === 0) return [0, 'inf']; // Horizontal line
const g = gcd(dx, dy);
return [dy / g, dx / g];
};
let maxPointsOnALine = 1;
// Iterate through each point
for (let i = 0; i < points.length; i++) {
const slopes = {};
for (let j = 0; j < points.length; j++) {
if (i !== j) {
const slope = getSlope(points[i], points[j]);
const slopeKey = slope.toString();
if (!slopes[slopeKey]) {
slopes[slopeKey] = 0;
}
slopes[slopeKey]++;
}
}
// Find the maximum number of points with the same slope for the current point
const currentMax = Math.max(...Object.values(slopes), 0) + 1;
maxPointsOnALine = Math.max(maxPointsOnALine, currentMax);
}
return maxPointsOnALine;
};Solution in Java
Java
import java.util.HashMap;
import java.util.Map;
class Solution {
// Helper function to calculate the greatest common divisor (GCD)
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// Helper function to get the slope between two points
private String getSlope(int[] p1, int[] p2) {
int dx = p2[0] - p1[0];
int dy = p2[1] - p1[1];
if (dx == 0) return "inf"; // Vertical line
if (dy == 0) return "0"; // Horizontal line
int g = gcd(dx, dy);
return (dy / g) + "/" + (dx / g);
}
public int maxPoints(int[][] points) {
if (points.length <= 1) {
return points.length;
}
int maxPointsOnALine = 1;
// Iterate through each point
for (int i = 0; i < points.length; i++) {
Map<String, Integer> slopes = new HashMap<>();
for (int j = 0; j < points.length; j++) {
if (i != j) {
String slope = getSlope(points[i], points[j]);
slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);
}
}
// Find the maximum number of points with the same slope for the current point
int currentMax = slopes.values().stream().max(Integer::compare).orElse(0) + 1;
maxPointsOnALine = Math.max(maxPointsOnALine, currentMax);
}
return maxPointsOnALine;
}
}Solution in C#
C#
using System;
using System.Collections.Generic;
public class Solution {
// Helper method to calculate the greatest common divisor (GCD)
private int Gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// Helper method to get the slope between two points
private string GetSlope(int[] p1, int[] p2) {
int dx = p2[0] - p1[0];
int dy = p2[1] - p1[1];
if (dx == 0) return "inf"; // Vertical line
if (dy == 0) return "0"; // Horizontal line
int g = Gcd(dx, dy);
return (dy / g) + "/" + (dx / g);
}
public int MaxPoints(int[][] points) {
if (points.Length <= 1) {
return points.Length;
}
int maxPointsOnALine = 1;
// Iterate through each point
for (int i = 0; i < points.Length; i++) {
Dictionary<string, int> slopes = new Dictionary<string, int>();
for (int j = 0; j < points.Length; j++) {
if (i != j) {
string slope = GetSlope(points[i], points[j]);
if (!slopes.ContainsKey(slope)) {
slopes[slope] = 0;
}
slopes[slope]++;
}
}
// Find the maximum number of points with the same slope for the current point
int currentMax = 0;
foreach (var count in slopes.Values) {
currentMax = Math.Max(currentMax, count);
}
currentMax += 1; // Include the base point
maxPointsOnALine = Math.Max(maxPointsOnALine, currentMax);
}
return maxPointsOnALine;
}
}