Domain 1EasyCORE

Check If It Is a Straight Line

The problem asks us to determine whether a set of given points in the XY plane lie on a straight line. The input is an array of coordinates where each coordinate is represented as `[x, y]`. The output should be `true` if all points are collinear (lie on the same straight line) and `false` otherwise.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Math#Geometry

1232. Check If It Is a Straight Line

Model: qwen2.5-coder:14b
Topics: Array,Math,Geometry
FAANG asked: 0
Acceptance rate: 43.2%


Problem Breakdown

The problem asks us to determine whether a set of given points in the XY plane lie on a straight line. The input is an array of coordinates where each coordinate is represented as [x, y]. The output should be true if all points are collinear (lie on the same straight line) and false otherwise.

Inputs:

  • An array of coordinates, coordinates[i] = [x, y].

Outputs:

  • A boolean value indicating whether the points form a straight line.

Implicit Constraints or Edge Cases:

  • The number of points is between 2 and 1000.
  • Each coordinate is within the range -10^4 <= x, y <= 10^4.
  • There are no duplicate points in the input array.

Intuition

A brute-force approach would involve checking if every pair of points has the same slope. However, this would be inefficient with a time complexity of O(n^2), which is not suitable given the constraints.

The key insight is to use the concept of slopes between points. If all points have the same slope relative to the first point, then they lie on a straight line. This can be checked using the formula for the slope between two points (x1, y1) and (x2, y2), which is (y2 - y1) / (x2 - x1). To avoid division and potential floating-point precision issues, we can use the cross-multiplication method: (y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1).

Approach

  1. Initial Check: If there are only two points, they trivially form a straight line.
  2. Calculate Slopes: For each subsequent point, calculate the slope using cross-multiplication to avoid division.
  3. Compare Slopes: Compare the calculated slopes with the slope between the first two points. If all slopes match, return true; otherwise, return false.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of coordinates. We iterate through the list once to check the slopes.
  • Space Complexity: O(1), as we only use a constant amount of extra space for variables.

Solution

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        # If there are only two points, they form a straight line
        if len(coordinates) == 2:
            return True
        
        # Calculate the initial slope using cross-multiplication
        x1, y1 = coordinates[0]
        x2, y2 = coordinates[1]
        
        for i in range(2, len(coordinates)):
            x3, y3 = coordinates[i]
            
            # Check if the current point has the same slope as the first two points
            if (y2 - y1) * (x3 - x2) != (y3 - y2) * (x2 - x1):
                return False
        
        return True

Edge Cases Handled

  • Two Points: The code correctly returns true for two points, as they trivially form a straight line.
  • Vertical Lines: The cross-multiplication method avoids division by zero issues that would occur with vertical lines (where x-coordinates are the same).
  • Horizontal Lines: Similarly, horizontal lines (where y-coordinates are the same) are handled correctly without any special cases.