LeetCode-in-Go

149. Max Points on a Line

Hard

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.

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: 4

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

Solution

func maxPoints(points [][]int) int {
	if len(points) < 2 {
		return len(points)
	}
	max := 0
	for i := 0; i < len(points); i++ {
		for j := i + 1; j < len(points); j++ {
			x := points[j][0] - points[i][0]
			y := points[j][1] - points[i][1]
			c := x*points[j][1] - y*points[j][0]
			count := 2
			for k := j + 1; k < len(points); k++ {
				if c == x*points[k][1]-y*points[k][0] {
					count++
				}
			}
			if count > max {
				max = count
			}
		}
	}
	return max
}

This site is open source. Improve this page.