Check If It Is a Straight Line solution and explanation
9 more videos on this problem
Check If It Is a Straight Line | Leetcode #1232 | Find if all coordinate points form a straight lineTechdose · 5:26 · 21K views
LeetCode 1232: Check If It Is a Straight Line - Interview Prep Ep 30Fisher Coder · 15:33 · 2K views
Leetcode 1232. Check If It Is a Straight LineCodeMeThere · 12:48 · 1K views
Check If It Is a Straight Line - 1232 Leetcode PythonPersistent Programmer · 8:49 · 1K views
Leetcode - Check If It Is a Straight Line (Python)Timothy H Chang · 7:50 · 886 views
Can You Detect a Straight Line? (LeetCode 1232: Check if it is a Straight Line)Code With Zi · 8:48 · 824 views
Leetcode 1232. Check If It Is a Straight Line [Java]if else statement · 5:34 · 794 views
Leetcode 1232: Check If It Is a Straight LineAlgorithms Casts · 16:28 · 419 views
Check If It Is a Straight Line LeetCode | LeetCode 1232 | Array, MathNaresh Gupta · 5:11 · 297 views
How to Solve "1232 Check if It Is a Straight Line" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 9:49 · 218 views
The problem
You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.
Example 1:
Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]] Output: true
Example 2:
Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]] Output: false
Constraints:
2 <= coordinates.length <= 1000coordinates[i].length == 2-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4coordinatescontains no duplicate point.
Approach overview
Problem Overview: You receive a list of 2D coordinates. The task is to determine whether every point lies on the same straight line. If the slope between every pair of consecutive points is identical, the points form a single line.
Approach 1: Using Slope Comparison (Time: O(n), Space: O(1))
This approach compares slopes between the first two points and every other pair of points. Compute the slope using (y2 - y1) / (x2 - x1). Instead of division, compare cross-multiplied values (y2 - y1) * (x - x1) and (y - y1) * (x2 - x1) to avoid floating point precision errors and division by zero. Iterate through the remaining coordinates and verify the slope consistency with the first segment. If any slope differs, the points do not form a straight line.
This method works well for problems involving coordinate relationships in geometry. It performs a single pass through the coordinates, so runtime is linear. Space remains constant since only a few variables store slope components.
Approach 2: Vector Cross Product (Time: O(n), Space: O(1))
A more geometric solution uses vector cross products. Form a base vector from the first two points: v = (x2 - x1, y2 - y1). For every other point, construct another vector from the first point: w = (xi - x1, yi - y1). If the cross product v.x * w.y - v.y * w.x equals zero, the vectors are collinear. Non-zero means the point deviates from the line.
This technique directly checks collinearity and avoids slope calculations entirely. It is common in computational geometry and works reliably even for vertical lines. Implementation requires only arithmetic operations while iterating once through the coordinate array. Time complexity remains O(n) with constant memory.
Recommended for interviews: Both solutions run in O(n) time and O(1) space, which is optimal because you must inspect every point. The vector cross product approach is often preferred in interviews since it avoids division and handles vertical lines naturally. Implementing slope comparison still demonstrates a strong understanding of coordinate geometry, while the cross product version signals deeper familiarity with geometric vector operations.
Approach 1: Approach 1: Using Slope Comparison
In this approach, we calculate the slope between the first two points and then compare this slope with that of subsequent points. The slope between two points (x1, y1) and (x2, y2) is given by (y2-y1)/(x2-x1). For all points to lie on the same line, this slope should be constant for every pair of consecutive points.
from typing import List
class Solution:
def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
x1, y1 = coordinates[0]
x2, y2 = coordinates[1]
for x, y in coordinates[2:]:
if (y2 - y1) * (x - x1) != (y - y1) * (x2 - x1):
return False
return Trueclass Solution {
public boolean checkStraightLine(int[][] coordinates) {
int x1 = coordinates[0][0], y1 = coordinates[0][1];
int x2 = coordinates[1][0], y2 = coordinates[1][1];
for (int i = 2; i < coordinates.length; i++) {
int x = coordinates[i][0], y = coordinates[i][1];
if ((y2 - y1) * (x - x1) != (y - y1) * (x2 - x1)) {
return false;
}
}
return true;
}
}#include <vector>
using namespace std;
bool checkStraightLine(vector<vector<int>>& coordinates) {
int x1 = coordinates[0][0], y1 = coordinates[0][1];
int x2 = coordinates[1][0], y2 = coordinates[1][1];
for (size_t i = 2; i < coordinates.size(); ++i) {
int x = coordinates[i][0], y = coordinates[i][1];
if ((y2 - y1) * (x - x1) != (y - y1) * (x2 - x1)) {
return false;
}
}
return true;
}var checkStraightLine = function(coordinates) {
const [x1, y1] = coordinates[0];
const [x2, y2] = coordinates[1];
for (let i = 2; i < coordinates.length; i++) {
const [x, y] = coordinates[i];
if ((y2 - y1) * (x - x1) !== (y - y1) * (x2 - x1)) {
return false;
}
}
return true;
};#include <stdbool.h>
bool checkStraightLine(int** coordinates, int coordinatesSize, int* coordinatesColSize) {
int x1 = coordinates[0][0], y1 = coordinates[0][1];
int x2 = coordinates[1][0], y2 = coordinates[1][1];
for (int i = 2; i < coordinatesSize; i++) {
int x = coordinates[i][0], y = coordinates[i][1];
if ((y2 - y1) * (x - x1) != (y - y1) * (x2 - x1)) {
return false;
}
}
return true;
}public class Solution {
public bool CheckStraightLine(int[][] coordinates) {
int x1 = coordinates[0][0], y1 = coordinates[0][1];
int x2 = coordinates[1][0], y2 = coordinates[1][1];
for (int i = 2; i < coordinates.Length; i++) {
int x = coordinates[i][0], y = coordinates[i][1];
if ((y2 - y1) * (x - x1) != (y - y1) * (x2 - x1)) {
return false;
}
}
return true;
}
}In this Python solution, a list slicing feature allows for seamless iteration from the third point. Cross product calculations confirm all points lie on a line.
Time Complexity: O(n), with n being the count of coordinates.
Space Complexity: O(1), maintaining constant space use.
Approach 2: Approach 2: Vector Cross Product
This approach uses the cross-product method which is useful for determining collinearity without explicitly calculating slopes. For every pair of consecutive vectors, compute the cross product to determine if they are collinear. If all cross products are zero, the points are collinear.
from typing import List
class Solution:
def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
dx = coordinates[1][0] - coordinates[0][0]
dy = coordinates[1][1] - coordinates[0][1]
for i in range(2, len(coordinates)):
x = coordinates[i][0] - coordinates[0][0]
y = coordinates[i][1] - coordinates[0][1]
if dx * y != dy * x:
return False
return Trueclass Solution {
public boolean checkStraightLine(int[][] coordinates) {
int dx = coordinates[1][0] - coordinates[0][0];
int dy = coordinates[1][1] - coordinates[0][1];
for (int i = 2; i < coordinates.length; i++) {
int x = coordinates[i][0] - coordinates[0][0];
int y = coordinates[i][1] - coordinates[0][1];
if (dx * y != dy * x) return false;
}
return true;
}
}#include <vector>
using namespace std;
bool checkStraightLine(vector<vector<int>>& coordinates) {
int dx = coordinates[1][0] - coordinates[0][0];
int dy = coordinates[1][1] - coordinates[0][1];
for (size_t i = 2; i < coordinates.size(); ++i) {
int x = coordinates[i][0] - coordinates[0][0];
int y = coordinates[i][1] - coordinates[0][1];
if (dx * y != dy * x) return false;
}
return true;
}var checkStraightLine = function(coordinates) {
const dx = coordinates[1][0] - coordinates[0][0];
const dy = coordinates[1][1] - coordinates[0][1];
for (let i = 2; i < coordinates.length; i++) {
const x = coordinates[i][0] - coordinates[0][0];
const y = coordinates[i][1] - coordinates[0][1];
if (dx * y !== dy * x) return false;
}
return true;
};#include <stdbool.h>
bool checkStraightLine(int** coordinates, int coordinatesSize, int* coordinatesColSize) {
int dx = coordinates[1][0] - coordinates[0][0];
int dy = coordinates[1][1] - coordinates[0][1];
for (int i = 2; i < coordinatesSize; ++i) {
int x = coordinates[i][0] - coordinates[0][0];
int y = coordinates[i][1] - coordinates[0][1];
if (dx * y != dy * x) { return false; }
}
return true;
}public class Solution {
public bool CheckStraightLine(int[][] coordinates) {
int dx = coordinates[1][0] - coordinates[0][0];
int dy = coordinates[1][1] - coordinates[0][1];
for (int i = 2; i < coordinates.Length; i++) {
int x = coordinates[i][0] - coordinates[0][0];
int y = coordinates[i][1] - coordinates[0][1];
if (dx * y != dy * x) return false;
}
return true;
}
}In Python, this solution uses consecutive point subtraction and subsequent cross product assessments to ensure that all points align perfectly on a direct path.
Time Complexity: O(n), reflecting coordinate count.
Space Complexity: O(1), sustaining minimum space usage.
Approach 3: Mathematics
The time complexity is O(n), where n is the length of the coordinates array. The space complexity is O(1).
func checkStraightLine(coordinates [][]int) bool {
x1, y1 := coordinates[0][0], coordinates[0][1]
x2, y2 := coordinates[1][0], coordinates[1][1]
for i := 2; i < len(coordinates); i++ {
x, y := coordinates[i][0], coordinates[i][1]
if (x-x1)*(y2-y1) != (y-y1)*(x2-x1) {
return false
}
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Slope Comparison | Time Complexity: O(n), with n being the count of coordinates. |
| Approach 2: Vector Cross Product | Time Complexity: O(n), reflecting coordinate count. |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Slope Comparison | O(n) | O(1) | Simple implementation when checking slope equality across coordinates |
| Vector Cross Product | O(n) | O(1) | Preferred geometric method that avoids division and handles vertical lines safely |
Frequently asked questions
Is Check If It Is a Straight Line easy or hard?
The problem is classified as Easy. It focuses on basic coordinate geometry and array iteration rather than complex data structures. Understanding slope relationships or vector cross products is enough to implement an optimal O(n) solution.
Check If It Is a Straight Line Python/Java solution
Python and Java implementations typically iterate through the coordinates and compute either slope equality or cross products. Both versions run in O(n) time and O(1) space. Python solutions often use tuple unpacking for coordinates, while Java uses integer arithmetic for cross product comparisons.
How to solve Check If It Is a Straight Line in O(n)?
Compute a base direction using the first two coordinates. For each remaining point, compare either the slope relationship or the vector cross product with the base segment. If any comparison fails, return false immediately. A single pass through the array ensures O(n) runtime with constant extra memory.
What is the best approach for Check If It Is a Straight Line?
The vector cross product approach is generally the best. It checks whether vectors formed from the first point and every other point are collinear. The condition v.x * w.y - v.y * w.x == 0 confirms that the points lie on the same line. This method runs in O(n) time and O(1) space and avoids division issues present in slope calculations.
Is Check If It Is a Straight Line asked at Google/Amazon/Meta?
This problem reflects common geometry and coordinate reasoning used in technical interviews. Variations of collinearity checks and slope comparisons appear in interviews at large tech companies including Google, Amazon, and Meta, particularly for roles emphasizing algorithmic fundamentals.
What data structure is used in Check If It Is a Straight Line?
The main structure is a simple array of coordinate pairs. The algorithm iterates through the array and performs mathematical comparisons between points. No additional data structures such as hash maps or stacks are required.
What is the time complexity of Check If It Is a Straight Line?
The optimal solution runs in O(n) time because every coordinate must be checked once. Each step performs constant-time arithmetic operations such as subtraction and multiplication. Space complexity is O(1) since only a few variables store coordinate differences.