LeetCode 335 - Self Crossing

The problem describes a path traced on a two-dimensional grid. We begin at the origin (0, 0) and move according to the values in the distance array.

leetcodehardarraymathgeometry

LeetCode Problem 335

Difficulty: 🔴 Hard
Topics: Array, Math, Geometry

Solution

Problem Understanding

The problem describes a path traced on a two-dimensional grid. We begin at the origin (0, 0) and move according to the values in the distance array. The movement directions always rotate counter-clockwise in the following repeating order:

  • north
  • west
  • south
  • east

Then the pattern repeats again.

For example, if distance = [2,1,1,2], the movement sequence is:

  • move 2 units north
  • move 1 unit west
  • move 1 unit south
  • move 2 units east

The task is to determine whether at any point the path intersects itself. A self crossing occurs when a newly drawn line segment overlaps or intersects any previous segment.

The important detail is that movement always happens in axis-aligned directions, which significantly simplifies the geometry. Every segment is either vertical or horizontal.

The constraints are large:

  • distance.length can be up to 10^5
  • each distance value can also be up to 10^5

These constraints immediately rule out expensive geometric intersection checks between every pair of segments. An O(n^2) solution would be far too slow for 10^5 movements.

Another important observation is that the movement pattern is highly structured. Because directions rotate in a fixed counter-clockwise order, only a small number of nearby segments can possibly intersect the current segment.

Several edge cases are especially important:

  • very short arrays cannot self-cross
  • overlapping segments count as crossings
  • touching exactly at endpoints also counts as crossing
  • spiral-like inward movement patterns frequently create intersections
  • equal-length movements can create special overlap cases that naive logic misses

A correct solution must carefully handle all of these scenarios.

Approaches

Brute Force Approach

The most straightforward solution is to explicitly construct every line segment and check the newly created segment against all previous non-adjacent segments.

For each move:

  1. Compute the segment endpoints.
  2. Compare the new segment against all earlier segments.
  3. If any intersection exists, return true.

This approach is correct because every possible crossing is explicitly checked using standard line segment intersection logic.

However, this becomes extremely expensive. If there are n segments, the total number of comparisons is approximately:

$$1 + 2 + 3 + \dots + (n-1) = O(n^2)$$

With n = 10^5, this is infeasible.

Optimal Observation

The key insight is that because movement directions rotate in a fixed counter-clockwise pattern, a segment can only intersect a very small set of previous segments.

As the path evolves, only three geometric crossing patterns are possible:

  1. The current line crosses the line 3 steps earlier.
  2. The current line overlaps the line 4 steps earlier.
  3. The current line crosses the line 5 steps earlier.

These patterns completely cover all possible self-crossings in this movement system.

This means we never need to store coordinates for all segments or perform general geometric intersection checks. We only need constant-time comparisons involving recent distances.

The solution therefore becomes a single linear scan through the array.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Explicitly constructs and compares all segments
Optimal O(n) O(1) Uses geometric crossing patterns specific to spiral movement

Algorithm Walkthrough

Geometric Cases

The optimal solution checks three specific crossing configurations.

Case 1: Current Line Crosses the Line 3 Steps Earlier

This is the simplest crossing pattern.

Suppose we are processing segment i.

The current segment crosses segment i-3 if:

$$distance[i] \ge distance[i-2]$$

and

$$distance[i-1] \le distance[i-3]$$

This corresponds to the path folding inward and intersecting itself.

Case 2: Current Line Overlaps the Line 4 Steps Earlier

This happens when the path forms a loop and the newest segment lands directly on top of an earlier segment.

Conditions:

$$distance[i-1] = distance[i-3]$$

and

$$distance[i] + distance[i-4] \ge distance[i-2]$$

Case 3: Current Line Crosses the Line 5 Steps Earlier

This is the most complicated inward spiral case.

Conditions:

$$distance[i-2] \ge distance[i-4]$$

$$distance[i] + distance[i-4] \ge distance[i-2]$$

$$distance[i-1] \le distance[i-3]$$

$$distance[i-1] + distance[i-5] \ge distance[i-3]$$

This captures the tight spiral intersection scenario.

Step-by-Step Algorithm

  1. Iterate through the array starting at index 3, because at least four segments are needed to create a crossing.
  2. For each index i, first check the simple crossing case against segment i-3.
  3. Then check the overlap case against segment i-4, if i >= 4.
  4. Then check the spiral crossing case against segment i-5, if i >= 5.
  5. If any condition is satisfied, immediately return true.
  6. If the loop finishes without detecting a crossing, return false.

Why it works

The movement directions are fixed and cyclic. Because of this structure, a newly added segment cannot intersect arbitrary distant segments. Any valid self-crossing must occur within one of the three local geometric configurations described above.

These three cases exhaust all possible ways a counter-clockwise spiral path can intersect itself. Since every new segment is checked against all valid crossing patterns, the algorithm is guaranteed to detect every self-crossing.

Python Solution

from typing import List

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        n = len(distance)

        for i in range(3, n):

            # Case 1:
            # Current line crosses the line 3 steps ahead
            if (
                distance[i] >= distance[i - 2]
                and distance[i - 1] <= distance[i - 3]
            ):
                return True

            # Case 2:
            # Current line overlaps the line 4 steps ahead
            if i >= 4:
                if (
                    distance[i - 1] == distance[i - 3]
                    and distance[i] + distance[i - 4] >= distance[i - 2]
                ):
                    return True

            # Case 3:
            # Current line crosses the line 5 steps ahead
            if i >= 5:
                if (
                    distance[i - 2] >= distance[i - 4]
                    and distance[i] + distance[i - 4] >= distance[i - 2]
                    and distance[i - 1] <= distance[i - 3]
                    and distance[i - 1] + distance[i - 5] >= distance[i - 3]
                ):
                    return True

        return False

The implementation directly mirrors the three geometric crossing cases discussed earlier.

The loop begins at index 3 because at least four segments are required before a crossing is possible.

The first condition checks whether the current segment intersects the segment three moves earlier. This is the most common self-crossing configuration and captures simple inward folds.

The second condition handles overlap cases. Equal-length opposite sides can cause the path to land directly on a previous segment instead of merely crossing it.

The third condition captures tighter inward spirals where the newest segment intersects the segment five moves earlier.

Each check uses only nearby indices, which keeps both time and space usage constant per iteration.

The moment a crossing is detected, the function immediately returns True. If no crossing occurs after processing all segments, the function returns False.

Go Solution

func isSelfCrossing(distance []int) bool {
	n := len(distance)

	for i := 3; i < n; i++ {

		// Case 1:
		// Current line crosses the line 3 steps earlier
		if distance[i] >= distance[i-2] &&
			distance[i-1] <= distance[i-3] {
			return true
		}

		// Case 2:
		// Current line overlaps the line 4 steps earlier
		if i >= 4 {
			if distance[i-1] == distance[i-3] &&
				distance[i]+distance[i-4] >= distance[i-2] {
				return true
			}
		}

		// Case 3:
		// Current line crosses the line 5 steps earlier
		if i >= 5 {
			if distance[i-2] >= distance[i-4] &&
				distance[i]+distance[i-4] >= distance[i-2] &&
				distance[i-1] <= distance[i-3] &&
				distance[i-1]+distance[i-5] >= distance[i-3] {
				return true
			}
		}
	}

	return false
}

The Go implementation is almost identical to the Python version because the algorithm only relies on index arithmetic and comparisons.

Go slices naturally support efficient indexed access, so no additional data structures are required.

Integer overflow is not a concern here because the maximum value involved is at most:

$$10^5 + 10^5 = 2 \times 10^5$$

which easily fits inside Go's int type.

Unlike Python, Go does not require explicit type hints or imports for this solution.

Worked Examples

Example 1

Input:

distance = [2,1,1,2]

Step Trace

i Current Distance Case Checked Result
3 2 Case 1 Crossing detected

At i = 3:

  • distance[3] = 2
  • distance[1] = 1
  • distance[2] = 1
  • distance[0] = 2

Check Case 1:

$$2 \ge 1$$

and

$$1 \le 2$$

Both conditions hold, so the path crosses itself.

Return true.

Example 2

Input:

distance = [1,2,3,4]

Step Trace

i Current Distance Case 1 Crossing
3 4 False No

At i = 3:

$$4 \ge 2$$

is true, but

$$3 \le 1$$

is false.

No crossing occurs.

Return false.

Example 3

Input:

distance = [1,1,1,2,1]

Step Trace

i Current Distance Case Triggered Crossing
3 2 None No
4 1 Case 3 Yes

At i = 4:

Case 1 fails.

Case 2 fails.

Case 3 conditions succeed, meaning the inward spiral intersects itself.

Return true.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each distance value is processed once
Space O(1) Only constant extra variables are used

The algorithm performs a single pass through the array. Every iteration performs only a small fixed number of comparisons, so the runtime grows linearly with the number of movements.

No auxiliary data structures are allocated. The solution only accesses nearby indices in the input array, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        n = len(distance)

        for i in range(3, n):

            if (
                distance[i] >= distance[i - 2]
                and distance[i - 1] <= distance[i - 3]
            ):
                return True

            if i >= 4:
                if (
                    distance[i - 1] == distance[i - 3]
                    and distance[i] + distance[i - 4] >= distance[i - 2]
                ):
                    return True

            if i >= 5:
                if (
                    distance[i - 2] >= distance[i - 4]
                    and distance[i] + distance[i - 4] >= distance[i - 2]
                    and distance[i - 1] <= distance[i - 3]
                    and distance[i - 1] + distance[i - 5] >= distance[i - 3]
                ):
                    return True

        return False

sol = Solution()

assert sol.isSelfCrossing([2,1,1,2]) is True   # Basic crossing
assert sol.isSelfCrossing([1,2,3,4]) is False  # Expanding spiral
assert sol.isSelfCrossing([1,1,1,2,1]) is True # Complex inward spiral

assert sol.isSelfCrossing([1]) is False        # Single segment
assert sol.isSelfCrossing([1,1]) is False      # Two segments
assert sol.isSelfCrossing([1,1,1]) is False    # Three segments

assert sol.isSelfCrossing([1,1,2,1,1]) is True # Endpoint touching
assert sol.isSelfCrossing([1,2,3,2,1,1]) is False # No crossing

assert sol.isSelfCrossing([1,1,2,2,1,1]) is True # Overlapping case
assert sol.isSelfCrossing([3,3,4,2,2]) is False  # Large outward path

assert sol.isSelfCrossing([1,2,2,1]) is True  # Immediate crossing
assert sol.isSelfCrossing([2,2,3,3,2,2]) is True # Spiral overlap
Test Why
[2,1,1,2] Basic self-crossing scenario
[1,2,3,4] Expanding spiral that never intersects
[1,1,1,2,1] Complex inward spiral crossing
[1] Minimum input size
[1,1] Too few segments to cross
[1,1,1] Still insufficient for crossing
[1,1,2,1,1] Endpoint-touching intersection
[1,2,3,2,1,1] Valid non-crossing inward turn
[1,1,2,2,1,1] Overlapping segment scenario
[3,3,4,2,2] Larger outward movement without crossing
[1,2,2,1] Immediate rectangular crossing
[2,2,3,3,2,2] Tight spiral overlap

Edge Cases

Very Small Arrays

Arrays with fewer than four movements cannot possibly self-cross because at least four segments are needed to form an intersection. A naive implementation might accidentally access negative indices or incorrectly report a crossing.

The implementation avoids this by beginning the loop at index 3.

Overlapping Segments

Crossing does not only mean perpendicular intersection. A segment landing directly on top of an earlier segment also counts.

For example:

[1,1,2,1,1]

creates an overlap situation rather than a standard cross.

This is why the second geometric condition exists. Without it, overlapping cases would be missed.

Tight Inward Spirals

Some inward spirals intersect only after several turns and do not satisfy the simple crossing condition.

For example:

[1,1,1,2,1]

requires the more advanced Case 3 logic.

Naive implementations that only compare against segment i-3 will incorrectly return false. The third condition ensures these deeper spiral crossings are properly detected.

Endpoint Touching

Touching exactly at a corner or endpoint still counts as a self-crossing.

This is why the implementation uses >= and <= comparisons rather than strict inequalities. Equal boundaries correctly identify endpoint contact as an intersection.