The task requires checking whether a given set of coordinates forms a straight line. By leveraging math concepts like slope and array processing, the solution can be efficiently implemented, especially when considering edge cases with only two points.
Problem Statement
You are given an array of coordinates where each element is a pair representing a point in the 2D plane. Your task is to determine if all the points lie on a single straight line.
To solve the problem, you can calculate the slope between consecutive points and check if all the slopes are the same. If they are, the points form a straight line.
Examples
Example 1
Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true
Example details omitted.
Example 2
Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]
Output: false
Example details omitted.
Constraints
- 2 <= coordinates.length <= 1000
- coordinates[i].length == 2
- -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
- coordinates contains no duplicate point.
Solution Approach
Calculate the Slope Between Points
To check if the points are collinear, calculate the slope between the first two points. The slope between two points (x1, y1) and (x2, y2) is given by (y2 - y1) / (x2 - x1). For the points to be on a straight line, the slope between each consecutive pair must be the same.
Use Cross Product to Avoid Division
To avoid division by zero and floating-point precision issues, use the cross product. For every consecutive pair of points, check if the cross product of the differences in x and y coordinates is zero. This method ensures accuracy without needing to compute actual slopes.
Edge Case Handling
If there are only two points, they always form a straight line. This edge case can be handled early in the solution to optimize performance. If the input array contains exactly two points, return true immediately.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The time complexity is O(n) since we only need to iterate through the points once to check the slope or cross product. The space complexity is O(1) as we only use a constant amount of extra space.
What Interviewers Usually Probe
- Candidate uses efficient math methods like slope or cross product to solve the problem.
- The solution handles edge cases, especially when there are only two points.
- Candidate explains the approach clearly, demonstrating understanding of geometry and array handling.
Common Pitfalls or Variants
Common pitfalls
- Overlooking the edge case of two points, which should always return true.
- Using division to calculate slopes, which can lead to precision issues or division by zero.
- Failing to consider all points in the array when checking for collinearity.
Follow-up variants
- Modify the problem to check for a straight line in 3D space using an additional z-coordinate.
- Ask the candidate to find if the points form a curve or parabola instead of a straight line.
- Extend the problem to handle multiple line segments and check if they form a continuous straight line.
How GhostInterview Helps
- GhostInterview helps by guiding candidates to the most efficient approach, ensuring they avoid unnecessary complications like floating-point precision errors.
- The platform provides examples and edge cases to encourage clear and structured problem-solving approaches, especially for math-heavy problems.
- GhostInterview also identifies common mistakes such as overlooking simple edge cases and using costly operations.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How can I determine if the points form a straight line?
You can check if the slopes between consecutive points are the same or use the cross product to avoid precision issues.
What if there are only two points?
Any two points always form a straight line, so you can immediately return true in this case.
Is it necessary to calculate the slope between every point?
You can optimize by using the cross product between points, which avoids floating-point issues and division by zero.
Can this problem be solved in less than O(n) time?
No, since you need to check all points at least once, the time complexity cannot be reduced below O(n).
How does GhostInterview help with solving math-based problems?
GhostInterview ensures you are aware of the most efficient techniques, like the cross product, and helps you avoid common mistakes in math-heavy questions.
Need direct help with Check If It Is a Straight Line instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Check If It Is a Straight Line from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Calculate the minimum seconds required to visit all given 2D points in order using optimal diagonal or straight moves.
Open problem page#1037 Valid BoomerangDetermine if three points on a 2D plane form a boomerang, based on distinctness and non-collinearity.
Open problem page#1030 Matrix Cells in Distance OrderCompute all matrix cell coordinates sorted by Manhattan distance from a given center using array and math techniques efficiently.
Open problem page