Check If It Is a Straight Line - Practice Coding Problems

Check If It Is a Straight Line - Problem

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

Note: A straight line requires at least 2 points. All points must lie on the same infinite line.

Approach: Use the slope formula to check if all points have the same slope relative to the first two points. To avoid division by zero, use cross multiplication: (y2-y1) * (x3-x1) = (y3-y1) * (x2-x1)

Input & Output

Example 1 — Basic Straight Line

$ Input: coordinates = [[1,2],[2,3],[3,4]]

› Output: true

💡 Note: All points lie on the line y = x + 1. Slope between any two points is 1.

Example 2 — Not a Straight Line

$ Input: coordinates = [[1,1],[2,2],[3,4]]

› Output: false

💡 Note: Points (1,1) and (2,2) have slope 1, but (2,2) and (3,4) have slope 2. Different slopes mean not a straight line.

Example 3 — Minimum Case

$ Input: coordinates = [[0,0],[1,1]]

› Output: true

💡 Note: Only two points - they always form a straight line by definition.

Constraints

2 ≤ coordinates.length ≤ 1000
coordinates[i].length == 2
-10⁴ ≤ coordinates[i][0], coordinates[i][1] ≤ 10⁴
coordinates contains no duplicate points

Visualization

Tap to expand

Understanding the Visualization

Input

Array of 2D coordinates [[x1,y1], [x2,y2], ...]

Process

Check if all points have same slope using cross multiplication

Output

Return true if collinear, false otherwise

Key Takeaway

🎯 Key Insight: Use cross multiplication to compare slopes without division, avoiding floating point precision issues

Asked in

A Amazon 15 G Google 12

The key insight is to use cross multiplication to avoid division when comparing slopes. Instead of calculating slope = (y2-y1)/(x2-x1), we use cross multiplication: (y2-y1)*(x3-x1) = (y3-y1)*(x2-x1). Best approach is the optimized single-pass solution. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(1)	Calculate slope between every pair of points and verify they're all equal
Optimized - Single Pass with Cross Multiplication	O(n)	O(1)	Use cross multiplication to avoid division and check all points in single pass

Brute Force - Check All Pairs — Algorithm Steps

Step 1: Calculate slope for first pair of points
Step 2: Compare slopes of all other pairs
Step 3: Return true if all slopes match

Visualization

Tap to expand

Step-by-Step Walkthrough

Get Reference

Calculate slope between first two points

Compare All

Check if every other point has same slope with first point

Result

Return true if all slopes match

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int coordinates[][2], int n) {
    if (n <= 2) return true;
    
    int x1 = coordinates[0][0], y1 = coordinates[0][1];
    int x2 = coordinates[1][0], y2 = coordinates[1][1];
    
    for (int i = 2; i < n; i++) {
        int x3 = coordinates[i][0], y3 = coordinates[i][1];
        if ((y2 - y1) * (x3 - x1) != (y3 - y1) * (x2 - x1)) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse 2D array manually
    int coordinates[1000][2];
    int count = 0;
    
    char* ptr = strchr(line, '[');
    ptr++; // Skip first [
    
    while ((ptr = strchr(ptr, '[')) != NULL) {
        ptr++;
        int x, y;
        sscanf(ptr, "%d,%d", &x, &y);
        coordinates[count][0] = x;
        coordinates[count][1] = y;
        count++;
        ptr = strchr(ptr, ']');
        if (ptr) ptr++;
    }
    
    bool result = solution(coordinates, count);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops to check all pairs of points

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for slope calculations

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler