algoadvance

Leetcode 1232. Check If It Is a Straight Line

Problem Statement

You are given an array coordinates, coordinates[i] = [x, y], where coordinates[i] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

Clarifying Questions

  1. What is the size range of the coordinates array?
    • The number of points and hence the length of coordinates will be at least 2 (since a line requires at least two points) but can go up to a reasonably large number, typically in the range ( [2, 10^4] ).
  2. Can the coordinates contain negative values?
    • Yes, coordinates can be negative as well as positive since they represent points in a 2D Cartesian plane.
  3. What is the expected output?
    • The function should return true if the points form a straight line, otherwise false.

Strategy

To determine if a set of points lies on a straight line, we can use the concept of slope. For any three points ((x_1, y_1)), ((x_2, y_2)), and ((x_3, y_3)), they are collinear (form a straight line) if and only if the slopes between the points are equal.

The slope between two points ((x_1, y_1)) and ((x_2, y_2)) is given by: [ \text{slope} = \frac{y_2 - y_1}{x_2 - x_1} ]

To avoid division and possible division by zero errors, we can cross-multiply to compare the slopes: [ (y_2 - y_1) \times (x_3 - x_2) = (y_3 - y_2) \times (x_2 - x_1) ]

If this condition holds true for every set of three consecutive points, then all the points are collinear.

Code

We will implement this strategy in the function checkStraightLine. Here’s how it can be coded in C++:

#include <vector>

using namespace std;

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        int dx = x1 - x0, dy = y1 - y0;
        
        for (int i = 2; i < coordinates.size(); ++i) {
            int xi = coordinates[i][0], yi = coordinates[i][1];
            if (dy * (xi - x1) != dx * (yi - y1)) {
                return false;
            }
        }
        return true;
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI