Maximum Collinear Points

Given a set of coordinates on a 2D plane, find the largest number of points that lie on the same straight line. This tests your ability to apply geometric principles and optimize for precision issues in calculations.

geometryhashingmathslopegreatest common divisor

Problem Statement

You are given an array of points, where each point is represented as a list of two integers [x, y] representing its coordinates on a two-dimensional plane. Your task is to determine the maximum number of points that lie on the same straight line. Return the largest count of such points.

Example 1

Input: [[1, 2], [2, 4], [3, 6], [0, 0]]

Output: 4

All four points lie on the line y = 2x.

Example 2

Input: [[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]]

Output: 3

The points [1, 1], [3, 2], and [5, 3] are collinear, and no other combination of 4 or more points are collinear.

Constraints

-The number of points in the input array will be between 1 and 300.
-Each point will be represented as a list of two integers.
-The x and y coordinates of each point will be between -10^4 and 10^4.
-The input array may contain duplicate points.
-All x, y coordinates will be integers.

Brute Force Approach

The most straightforward way to solve this is to check every possible line formed by each pair of points. Imagine you're a surveyor trying to find the longest straight path across a field. You'd pick two points, draw a line, and then check if every other point falls on that line. This involves calculating the slope and y-intercept for each pair and comparing it to all other points, resulting in a lot of calculations.

TimeO(n^3)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem