What is the time complexity of Check If It Is a Straight Line?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Check If It Is a Straight Line?

This problem uses Array, Math, Geometry. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Check If It Is a Straight Line?

**Integer Cross-Product for Collinearity:** Instead of calculating and comparing floating-point slopes, which introduces precision issues and division-by-zero problems (especially for vertical lines), the solution leverages the fact that three points `(x0, y0)`, `(x1, y1)`, and `(x, y)` are collinear if and only if `(x1 - x0) * (y - y0) == (x - x0) * (y1 - y0)`. This algebraic manipulation of `slope_01 == slope_0i` allows for a robust, purely integer-based check. **Reference Line from First Two Points:** Any two distinct points define a unique straight line. The solution wisely uses the first two points in the `coordinates` array (`coordinates[0]` and `coordinates[1]`) to establish this foundational line. All subsequent points are then checked against this *single, fixed* line, simplifying the logic significantly compared to comparing every possible pair of points.

Which companies ask LeetCode 1232. Check If It Is a Straight Line in interviews?

This problem is frequently asked at Datadog, Palantir Technologies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Check If It Is a Straight Line - LeetCode 1232 Solution

Q: How to solve Check If It Is a Straight Line?

The provided solution elegantly navigates the common pitfalls of direct slope calculation (like floating-point inaccuracies or division by zero for vertical lines) by reframing the collinearity check. It establishes a reference line using the very first two points, `(x0, y0)` and `(x1, y1)`. For every subsequent point `(x, y)` in the `coordinates` array, it checks if it aligns with this established line. The core insight lies in transforming the slope equality `(y - y0) / (x - x0) == (y1 - y0) / (x1 - x0)` into a cross-multiplication form: `(x1 - x0) * (y - y0) == (x - x0) * (y1 - y0)`. This effectively checks if the 'cross-product' of the vector from `(x0, y0)` to `(x1, y1)` and the vector from `(x0, y0)` to `(x, y)` is zero. If this equality holds, the points are collinear; if the products are unequal (`!=`), the point `(x, y)` does not lie on the line, and the function immediately returns `false`. This approach uses only integer arithmetic, ensuring precision and robustly handling all line orientations, including horizontal and vertical ones.

Check If It Is a Straight Line - Complete Solution Guide

Check If It Is a Straight Line is LeetCode problem 1232, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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

Detailed Explanation

The task is to determine if a given set of `coordinates` points all lie on a single straight line within the XY plane. Each `coordinates[i]` is provided as an `[x, y]` pair. Essentially, we're asked to verify if every point is collinear with all others. For instance, if you're given `[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]`, the function should return `true` because these points form a clear diagonal line where `y = x + 1`. However, for `[[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]`, the output should be `false` because `[3,4]` deviates from the `y=x` pattern established by the first two points.

Solution Approach

The provided solution elegantly navigates the common pitfalls of direct slope calculation (like floating-point inaccuracies or division by zero for vertical lines) by reframing the collinearity check. It establishes a reference line using the very first two points, `(x0, y0)` and `(x1, y1)`. For every subsequent point `(x, y)` in the `coordinates` array, it checks if it aligns with this established line. The core insight lies in transforming the slope equality `(y - y0) / (x - x0) == (y1 - y0) / (x1 - x0)` into a cross-multiplication form: `(x1 - x0) * (y - y0) == (x - x0) * (y1 - y0)`. This effectively checks if the 'cross-product' of the vector from `(x0, y0)` to `(x1, y1)` and the vector from `(x0, y0)` to `(x, y)` is zero. If this equality holds, the points are collinear; if the products are unequal (`!=`), the point `(x, y)` does not lie on the line, and the function immediately returns `false`. This approach uses only integer arithmetic, ensuring precision and robustly handling all line orientations, including horizontal and vertical ones.

Step-by-Step Algorithm

Step 1: Handle the base case: If the number of points is less than or equal to 2, return `true`.
Step 2: Select two reference points (e.g., the first two points in the array).
Step 3: Iterate through the remaining points.
Step 4: For each point, calculate the cross product using the formula: (x1 - x0)(y - y0) - (x - x0)(y1 - y0), where (x0, y0) and (x1, y1) are the reference points and (x, y) is the current point. If this cross product is non-zero, the points are not collinear, and the function returns `false`.
Step 5: If the loop completes without finding any non-collinear points, return `true`.

Key Insights

**Integer Cross-Product for Collinearity:** Instead of calculating and comparing floating-point slopes, which introduces precision issues and division-by-zero problems (especially for vertical lines), the solution leverages the fact that three points `(x0, y0)`, `(x1, y1)`, and `(x, y)` are collinear if and only if `(x1 - x0) * (y - y0) == (x - x0) * (y1 - y0)`. This algebraic manipulation of `slope_01 == slope_0i` allows for a robust, purely integer-based check.
**Reference Line from First Two Points:** Any two distinct points define a unique straight line. The solution wisely uses the first two points in the `coordinates` array (`coordinates[0]` and `coordinates[1]`) to establish this foundational line. All subsequent points are then checked against this *single, fixed* line, simplifying the logic significantly compared to comparing every possible pair of points.
**Early Exit for Efficiency:** The algorithm incorporates an immediate `return False` as soon as it encounters a point that violates the collinearity condition. If even one point is off the line, the entire set cannot form a straight line, so there's no need to continue processing the remaining points. This short-circuiting behavior provides an efficient optimization, especially for inputs where the points quickly diverge from a straight line.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Math, Geometry.

Companies

Asked at: Datadog, Palantir Technologies.

Check If It Is a Straight Line | LeetCode 1232

Easy

Array Math Geometry

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        if (coordinates.length <= 2) {
            return true;
        }

        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        double slope;

        if (x1 - x0 == 0) {
            for (int i = 2; i < coordinates.length; i++) {
                if (coordinates[i][0] - x0 != 0) {
                    return false;
                }
            }
            return true;
        } else {
            slope = (double) (y1 - y0) / (x1 - x0);
            for (int i = 2; i < coordinates.length; i++) {
                double currentSlope;
                if (coordinates[i][0] - x0 == 0) {
                     return false;
                } else {
                    currentSlope = (double) (coordinates[i][1] - y0) / (coordinates[i][0] - x0);
                }
                if (currentSlope != slope) {
                    return false;
                }
            }
            return true;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1232: Check If It Is a Straight Line - Detailed explanation and solution approaches.

Topics

Array Math Geometry

Companies

DatadogPalantir Technologies

Stats

Difficulty:Easy

Languages:4

Companies:2

Problem #:1232

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Handle the base case: If the number of points is less than or equal to 2, return `true`.
2
Step 2: Select two reference points (e.g., the first two points in the array).
3
Step 3: Iterate through the remaining points.
4
Step 4: For each point, calculate the cross product using the formula: (x1 - x0)(y - y0) - (x - x0)(y1 - y0), where (x0, y0) and (x1, y1) are the reference points and (x, y) is the current point. If this cross product is non-zero, the points are not collinear, and the function returns `false`.
5
Step 5: If the loop completes without finding any non-collinear points, return `true`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm involves a single loop that iterates through the points. The space used by variables is constant and doesn't depend on the input size. Therefore, the time complexity is linear and space complexity is constant.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Slope Calculation (with handling for vertical lines)

Calculate the slope between the first two points. Then, iterate through the remaining points and verify that the slope between each point and the first point is the same (handling the vertical case separately where the x-coordinate is constant).

Time: O(n)Space: O(1)

Trade-offs: This approach might be slightly less efficient than the cross-product method due to the need for explicit handling of vertical lines. The cross-product method is more concise and avoids potential division-by-zero errors.

✨

Key Insights

1**Integer Cross-Product for Collinearity:** Instead of calculating and comparing floating-point slopes, which introduces precision issues and division-by-zero problems (especially for vertical lines), the solution leverages the fact that three points `(x0, y0)`, `(x1, y1)`, and `(x, y)` are collinear if and only if `(x1 - x0) * (y - y0) == (x - x0) * (y1 - y0)`. This algebraic manipulation of `slope_01 == slope_0i` allows for a robust, purely integer-based check.
2**Reference Line from First Two Points:** Any two distinct points define a unique straight line. The solution wisely uses the first two points in the `coordinates` array (`coordinates[0]` and `coordinates[1]`) to establish this foundational line. All subsequent points are then checked against this *single, fixed* line, simplifying the logic significantly compared to comparing every possible pair of points.
3**Early Exit for Efficiency:** The algorithm incorporates an immediate `return False` as soon as it encounters a point that violates the collinearity condition. If even one point is off the line, the entire set cannot form a straight line, so there's no need to continue processing the remaining points. This short-circuiting behavior provides an efficient optimization, especially for inputs where the points quickly diverge from a straight line.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Vertical lines: The Java solution explicitly handles the case where the slope is undefined (vertical line). The other solutions implicitly handle this because the cross-product method still works correctly even when x1 - x0 is zero.
Edge case 2: Only two points: The algorithm correctly handles the case where there are only two points, which always form a straight line.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the edge case of vertical lines. Direct slope calculation leads to division by zero if the line is vertical. The cross product avoids this.

✗Common mistake 2: Incorrectly implementing the cross-product formula. A small error in the formula will lead to inaccurate results.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Image processing: Identifying collinear pixels in an image for tasks like edge detection or line recognition.

🏦Real-world scenario 2: GPS tracking: Determining if a series of GPS coordinates roughly represent a straight path (allowing for small variations due to GPS inaccuracy).

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 31, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Check If It Is a Straight Line"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether math techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?