284. All in a Row
A surveyor hammers flags into a flat field and records their positions as points, where points[i] = [x, y]. Decide whether one single straight line can run through every flag. Several flags may share exactly the same position; a field with one flag, or with all flags stacked on one spot, counts as a straight row, and so does any pair of flags. Return true if such a line exists, otherwise false.
Avoid slopes and division: compare integer cross products. Beware the trap of anchoring on two flags that happen to coincide. Aim for O(n) time and O(1) extra space.
Example 1
- Input:
- points = [[4,9],[10,21],[-2,-3],[7,15]]
- Output:
- true
- Explanation:
Every flag sits on the line y = 2x + 1, so they all lie in a row.
Example 2
- Input:
- points = [[0,0],[5,1],[10,3]]
- Output:
- false
- Explanation:
The middle flag is off the line through the outer two, so the answer is false.
Example 3
- Input:
- points = [[3,3],[3,3],[8,-2],[3,3]]
- Output:
- true
- Explanation:
Only two distinct locations occur, and any two locations lie on a common line.
Constraints
1 ≤ points.length ≤ 1200
-105 ≤ x, y ≤ 105 (so every cross product stays below 1011 and is exact in 64-bit integers and in JavaScript numbers)
Points need not be distinct.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)