Abstract / Summary

Given a set of points determine if all lie on a single straight path

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 40% (700k+ submissions).

Typical patterns to solve this problem:

• Array
• Geometry
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The function determines whether a set of 2-D points, supplied as a vector of integer pairs, all lie on a single straight line. It first checks for the trivial cases of a purely vertical or horizontal line, then computes a reference slope using the first two points and verifies that every subsequent point yields the same slope within a tight tolerance.

Initial Horizontal/Vertical Check

The algorithm extracts the x- and y-coordinates of the first point and uses two Boolean flags, xonly and yonly, to track whether all points share the same x-value (vertical line) or the same y-value (horizontal line). The loop iterates over each coordinate pair, clearing the flags as soon as a differing value is observed. An early break stops the scan once both flags are false, avoiding unnecessary work.

int x1 = coordinates[0][0];
int y1 = coordinates[0][1];
bool xonly = true;
bool yonly = true;
for (auto c : coordinates)
{
    if (c[0] != x1)
        xonly = false;
    if (c[1] != y1)
        yonly = false;

    if (!xonly && !yonly)
        break;
}
if (xonly || yonly)
    return true;

If either flag remains true after the scan, the points are confirmed to be collinear on a vertical or horizontal line, and the function returns true immediately.

Slope Calculation

When the points are not all aligned vertically or horizontally, the code computes the differences in x and y between the first two points to obtain a reference slope r. A very small epsilon (1e-15) is defined to tolerate floating-point rounding errors.

int dx = coordinates[0][0] - coordinates[1][0];
int dy = coordinates[0][1] - coordinates[1][1];
double epsilon = 1e-15;
double r = double(dx) / dy;

The division is performed in double precision to preserve accuracy for non-integer slopes.

Iterative Verification

Starting from the third point, the algorithm recomputes the differences relative to the first point, derives a new slope r2, and compares it to the reference slope r. The absolute difference is scaled by a factor of 1000 times epsilon to provide a practical tolerance. If any point deviates beyond this bound, the function returns false. The loop stops as soon as a mismatch is detected, ensuring minimal work.

for (int i = 2; i < coordinates.size(); i++)
{
    dx = coordinates[i][0] - coordinates[0][0];
    dy = coordinates[i][1] - coordinates[0][1];
    double r2 = double(dx) / dy;

    if (fabs(r2 - r) > 1000*epsilon)
        return false;
}
return true;

Edge Cases Handled

The early vertical/horizontal detection prevents division by zero when the line is perfectly vertical (dy == 0) or horizontal (dx == 0). The same-point scenario, where all coordinates are identical, satisfies both xonly and yonly, causing an immediate true result. The use of a scaled epsilon accommodates the limited precision of floating-point arithmetic, ensuring that points that mathematically lie on the same line but produce minute numerical differences are still accepted.

Performance Optimizations

The code employs several techniques to reduce runtime overhead. The initial scan for uniform x or y values can terminate early once both flags are cleared, avoiding a full traversal of the input when the line is neither vertical nor horizontal. The slope verification loop also exits at the first sign of inconsistency, preventing unnecessary calculations for large datasets. All arithmetic operations are simple integer subtractions followed by a single double division per iteration, keeping the computational cost low. The use of a static epsilon and a constant scaling factor eliminates the need for dynamic tolerance computation.

Imagine you have a bunch of dots scattered on a big piece of paper. This code acts like a little detective to see if all those dots form one perfectly straight line, just like when you use a ruler to draw.

First, the code looks at the very first dot and checks if every other dot is lined up perfectly straight up and down or straight across from side to side. It creates two imaginary paths to see if the dots stay on them.

If the dots are tilting on a slant instead of being perfectly flat or straight up, the code needs to be a bit more clever. It looks at the first two dots to see how steep the slant is. Think of this like checking the angle of a slide at the playground. Once it knows how steep that first bit is, it goes through every single other dot one by one. It measures the distance between the starting dot and each new dot to see if they all follow that same exact slope.

By looking at that slope for every single dot, the code can tell if they are all part of the same straight path. If every dot follows the same angle, the code says the line is straight. If even one dot is a little bit off to the side, it knows the line is wobbly and not perfectly straight.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem						Ruby
	fpdjsns	C++
	fsq	C++
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	lzl124631x	C++
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality