Code Implementation

class Solution:
    def isSelfCrossing(self, x):
        n = len(x)
        for i in range(3, n):
            # Case 1: current line crosses the line 3 steps ahead
            if x[i] >= x[i-2] and x[i-1] <= x[i-3]:
                return True
            # Case 2: current line overlaps the line 4 steps ahead
            if i >= 4:
                if x[i-1] == x[i-3] and x[i] + x[i-4] >= x[i-2]:
                    return True
            # Case 3: current line crosses the line 5 steps ahead
            if i >= 5:
                if x[i-2] >= x[i-4] and x[i] + x[i-4] >= x[i-2] and x[i-1] <= x[i-3] and x[i-1] + x[i-5] >= x[i-3]:
                    return True
        return False
      

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        int n = x.size();
        for (int i = 3; i < n; ++i) {
            // Case 1
            if (x[i] >= x[i-2] && x[i-1] <= x[i-3])
                return true;
            // Case 2
            if (i >= 4) {
                if (x[i-1] == x[i-3] && x[i] + x[i-4] >= x[i-2])
                    return true;
            }
            // Case 3
            if (i >= 5) {
                if (x[i-2] >= x[i-4] &&
                    x[i] + x[i-4] >= x[i-2] &&
                    x[i-1] <= x[i-3] &&
                    x[i-1] + x[i-5] >= x[i-3])
                    return true;
            }
        }
        return false;
    }
};
      

class Solution {
    public boolean isSelfCrossing(int[] x) {
        int n = x.length;
        for (int i = 3; i < n; ++i) {
            // Case 1
            if (x[i] >= x[i-2] && x[i-1] <= x[i-3])
                return true;
            // Case 2
            if (i >= 4) {
                if (x[i-1] == x[i-3] && x[i] + x[i-4] >= x[i-2])
                    return true;
            }
            // Case 3
            if (i >= 5) {
                if (x[i-2] >= x[i-4] &&
                    x[i] + x[i-4] >= x[i-2] &&
                    x[i-1] <= x[i-3] &&
                    x[i-1] + x[i-5] >= x[i-3])
                    return true;
            }
        }
        return false;
    }
}
      

var isSelfCrossing = function(x) {
    let n = x.length;
    for (let i = 3; i < n; ++i) {
        // Case 1
        if (x[i] >= x[i-2] && x[i-1] <= x[i-3])
            return true;
        // Case 2
        if (i >= 4) {
            if (x[i-1] === x[i-3] && x[i] + x[i-4] >= x[i-2])
                return true;
        }
        // Case 3
        if (i >= 5) {
            if (x[i-2] >= x[i-4] &&
                x[i] + x[i-4] >= x[i-2] &&
                x[i-1] <= x[i-3] &&
                x[i-1] + x[i-5] >= x[i-3])
                return true;
        }
    }
    return false;
};
      

Problem Description

You are given an array x of positive integers representing the distance moved in each step, following a specific pattern:

• Start at the origin (0, 0) and move in the following order: north, west, south, east, and repeat counter-clockwise.
• Each x[i] is the distance moved in the i-th direction.

• 1 ≤ x.length ≤ 10⁵
• 0 ≤ x[i] ≤ 10⁶

Return true if the path crosses itself, otherwise return false.

Thought Process

The first instinct might be to simulate the path and keep track of all the segments, checking if the current move crosses any previous segment. However, this would require storing all past segments and checking for intersections, which would be too slow for large inputs.

On closer inspection, we notice that the path is always turning 90 degrees counter-clockwise, and only the most recent segments can possibly be crossed by the current segment. This observation allows us to focus only on a fixed number of previous segments (at most 5), greatly simplifying the problem.

The challenge is to identify the geometric conditions under which the path can cross itself, and to encode those as simple checks.

Solution Approach

The solution is based on the fact that, due to the regular turning pattern, only the last few segments (at most 5) can be crossed by the current segment. We check for three possible crossing scenarios at each step:

• Case 1: The current segment crosses the segment 3 steps before (forms a simple loop).
• Case 2: The current segment overlaps with the segment 4 steps before (forms a "touching" overlap).
• Case 3: The current segment crosses the segment 5 steps before (forms a spiral that crosses itself).

1. Iterate through the array starting from the fourth element (since you need at least 4 moves to cross).
2. For each position i, check if any of the three cases apply using the lengths of the last few moves.
3. If any case is true, return true immediately.
4. If the loop finishes without finding a crossing, return false.

Example Walkthrough

Let's take the input x = [2, 1, 1, 2]:

• Step 0: Go north 2 units.
• Step 1: Go west 1 unit.
• Step 2: Go south 1 unit.
• Step 3: Go east 2 units.

• We check if x[3] >= x[1] and x[2] <= x[0]: 2 >= 1 and 1 <= 2 are both true.
• This matches Case 1: the path crosses itself (forming a simple loop).

Time and Space Complexity

Brute-force approach:

• Time: O(n²), since each new segment could be checked against all previous segments.
• Space: O(n), to store all previous segments.

• Time: O(n), since we only do a constant number of checks at each step.
• Space: O(1), since we do not store the path, just use a few variables for recent moves.

Summary

The Self Crossing problem demonstrates how understanding the geometric structure of a problem can lead to a highly efficient solution. By recognizing that only the last few moves are relevant for crossing, we avoid unnecessary computations and storage. The key insight is to check for three specific crossing patterns at each step, leading to a simple and elegant O(n) time, O(1) space algorithm.