Abstract / Summary

You must determine if a path made of straight lines crosses itself at any point.

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 36% (100k+ 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 provided implementation determines whether a polyline described by a sequence of step lengths crosses itself. The algorithm processes the distance array in a single forward pass, maintaining a sliding window of the most recent six segment lengths. By comparing the current segment with earlier ones, it detects the three geometric configurations that constitute a self-intersection. The early return for arrays shorter than four elements reflects the fact that a crossing cannot occur with fewer than four moves.

Key Steps

Initial length check

The function first obtains the number of steps and immediately returns False when the count is less than four. This guard eliminates unnecessary work for trivial inputs.

size = len(distance)
if size < 4:
    return False

Window initialization

The first three distances are unpacked into variables c, b, and a. Two additional placeholders d and e are set to negative infinity, ensuring that the first few comparisons involving these values behave correctly without extra conditional logic.

c, b, a = distance[:3]
d = e = -inf

Iterative processing

Starting from the fourth element, the loop shifts the six-element window forward. The assignment simultaneously updates all window variables: the new distance becomes a, the previous a becomes b, and so on, while the oldest values move into d and e.

for i in range(3, size):
    a, b, c, d, e, f = distance[i], a, b, c, d, e

Detection of shrinking vs. growing pattern

The first conditional checks whether the current segment (a) is at least as long as the segment three steps earlier (c) while the segment immediately before (b) does not exceed the segment four steps earlier (d). This pattern indicates that the path is expanding in one direction while contracting in another, which forces a crossing.

if a >= c and b <= d:
    return True

Overlap with a segment from a full rotation ago

The second conditional captures the situation where the current segment aligns exactly with the segment three steps earlier (b == d) and the segment two steps earlier (c) is short enough to allow the current segment to reach or pass the line drawn a full turn earlier (c <= a + e). This corresponds to a “touching” case where the path meets a previous line without necessarily crossing it.

if b == d and c <= a + e:
    return True

Complex crossing scenario

The third conditional handles a more intricate geometry where the current segment (a) is long enough to reach back toward the segment three steps earlier, but not so long as to completely overlap it (a >= c - e). Simultaneously, the preceding segment (b) must be long enough to intersect the segment four steps earlier (b >= d - f) while still being constrained by the earlier segment (b <= d). The additional checks c >= e ensure that the relevant earlier segments exist with sufficient length. When all these relations hold, a self-crossing is guaranteed.

if a >= c - e and b >= d - f and \
   c >= e     and b <= d:
    return True

Final result

If none of the crossing conditions are satisfied throughout the traversal, the function concludes that the path does not intersect itself and returns False.

return False

Edge Cases Handled

The algorithm explicitly accommodates several subtle configurations:

• Paths that begin to shrink after an initial expansion are caught by the first conditional, which looks for a simultaneous increase (a >= c) and decrease (b <= d) across non-adjacent segments.
• Exact alignment of a segment with a line drawn a full rotation earlier is detected by the second conditional, covering cases where the path “touches” a previous segment without overtly crossing it.
• Scenarios where the current segment reaches back toward a prior segment but does not fully overlap, while the preceding segment also reaches back toward an even earlier line, are captured by the third conditional. This handles the classic “spiral-in” crossing pattern that requires checking two pairs of non-adjacent segments.
• The initialization of d and e to negative infinity ensures that the first few iterations, where not all six window positions are populated, still evaluate safely without additional boundary checks.

Performance Optimizations

The implementation achieves constant-time work per iteration by maintaining a fixed-size sliding window of six variables. This eliminates the need for indexing into the original list beyond the current element, reducing memory accesses. The use of simultaneous multiple assignment (a, b, c, d, e, f = ...) updates all window variables in a single Python statement, which is more efficient than separate assignments. Early termination on the first detection of a crossing prevents unnecessary processing of the remaining steps, providing best-case speed when a crossing occurs early in the sequence. The guard clause for inputs shorter than four elements avoids entering the loop altogether for trivial cases. All these choices keep the runtime linear in the number of distance entries while using only a handful of scalar variables.

Imagine drawing a long line with a crayon on a big piece of paper. You turn at every corner to make a shape that keeps spiraling, either getting bigger or getting smaller. Sometimes, if the lines are not careful, they might crash into each other.

To keep track of where the lines are going, the code keeps a list of how long each movement is. Because it is impossible to crash if you only draw three lines, the code first checks if there are at least four.

As the drawing continues, the code looks at the last few lines to see how they are behaving. It constantly compares the new line with the ones drawn just before it.

The first rule in the code checks if the path is trying to grow and shrink at the same time, which is like trying to go left and right at once, causing a bump. The second rule checks if a new line happens to touch an old line from way back when the drawing started. The third rule looks for a special case where the path wraps around to close a loop. Every time a new line is added, the computer checks these rules to see if the crayon has crossed over a path that was already drawn.

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++			Java				Python	TS
	WalkCCC	C++			Java				Python
	leetcode.ca	C++			Java	C#	Bash	Go	Python
	LeetcodeHelp	C++			Java				Python
	MemoryLimitExceeded	C++							Python
	Progiez	C++			Java				Python
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	linouk23	C++
	lzl124631x	C++
	ruoru			Rust
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	Bash, C++, C#, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
linouk23	C++
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
wisdompeak	C++

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