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.

Description Hints 3 Solution Video 5:26

1232. Check If It Is a Straight Line

Easy40.1% acceptance3 companies

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.

Asked at 3 companies

Palantir Datadog Amazon

Topics

Hints open one at a time

Hint 1

If there're only 2 points, return true.

Hint 2

Check if all other points lie on the line defined by the first 2 points.

Hint 3

Use cross product to check collinearity.

5:26

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]

Input

[[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]

Your code is saved on this device.Solution