Skip to main content
Talentd

Check If It Is a Straight Line - Solution & Explanation

EasyArrayMathGeometry12 min readAsked at: Amazon, Palantir, Datadog
Practice this problem

Problem Statement

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 <= 1000
  • coordinates[i].length == 2
  • -10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
  • coordinates contains 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.

This C solution checks the constancy of slope using cross multiplication to avoid division and potential floating point precision issues. It iterates through all points starting from the third point and compares the calculated product terms for collinearity.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), as we use a fixed number of extra variables.

Try this approach in the editor →

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.

This C solution utilizes the vector cross-product to determine if any vectors are non-collinear by checking if the cross-product between consecutive points remains zero.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n refers to the number of coordinates.
Space Complexity: O(1), as only constant additional space is used.

Try this approach in the editor →

Approach 3: Mathematics

The time complexity is O(n), where n is the length of the coordinates array. The space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Slope Comparison

Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), as we use a fixed number of extra variables.

Approach 2: Vector Cross Product

Time Complexity: O(n), where n refers to the number of coordinates.
Space Complexity: O(1), as only constant additional space is used.

Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Slope ComparisonO(n)O(1)Simple implementation when checking slope equality across coordinates
Vector Cross ProductO(n)O(1)Preferred geometric method that avoids division and handles vertical lines safely

Video Solution

Check If It Is a Straight Line | Leetcode #1232 | Find if all coordinate points form a straight line • Techdose • 21,067 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Check If It Is a Straight Line with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays