# Self Crossing
**Difficulty:** HARD
[External](https://leetcode.com/problems/self-crossing)
Canonical: https://scaleengineer.com/dsa/problems/self-crossing
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
**Companies:** [Zomato](https://scaleengineer.com/companies/zomato)
---
## Problem
You are given an array of integers `distance`.

You start at the point `(0, 0)` on an **X-Y plane,** and you move `distance[0]` meters to the north, then `distance[1]` meters to the west, `distance[2]` meters to the south, `distance[3]` meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise.

Return `true` _if your path crosses itself or_ `false` _if it does not_.

**Example 1:**

![](https://assets.glich.co/dsa/self-crossing/image0.jpg) 

**Input:** distance = [2,1,1,2]
**Output:** true
**Explanation:** The path crosses itself at the point (0, 1).

**Example 2:**

![](https://assets.glich.co/dsa/self-crossing/image1.jpg) 

**Input:** distance = [1,2,3,4]
**Output:** false
**Explanation:** The path does not cross itself at any point.

**Example 3:**

![](https://assets.glich.co/dsa/self-crossing/image2.jpg) 

**Input:** distance = [1,1,1,2,1]
**Output:** true
**Explanation:** The path crosses itself at the point (0, 0).

**Constraints:**

* `1 <= distance.length <= 105`
* `1 <= distance[i] <= 105`

# Approaches
## Brute-force Simulation with Intersection Check
This approach simulates the path-drawing process step by step. For each new line segment being drawn, we check if it intersects with any of the previous non-adjacent segments. If an intersection is found at any point, we can immediately conclude that the path crosses itself.
**Time:** O(N^2), where N is the length of the `distance` array. For each of the N segments, we iterate through up to O(N) previous segments to check for intersections. The intersection check itself is O(1). · **Space:** O(N), where N is the length of the `distance` array. We need to store the coordinates of all N line segments.
**Pros:** Conceptually simple and easy to follow.; Directly models the problem statement.
**Cons:** Highly inefficient due to the nested loop structure.; The space requirement grows linearly with the input size.; Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for large inputs.
### Explanation
The core idea is to maintain a list of all line segments that constitute the path. As we generate each new segment based on the `distance` array, we perform an intersection test against all segments already in our list, except for the one immediately preceding it (as adjacent segments naturally touch at a vertex, which isn't considered a crossing unless they overlap).

Since the path consists only of North, West, South, and East movements, all segments are either perfectly horizontal or vertical. This simplifies the intersection check between two segments. A horizontal segment and a vertical segment cross if the x-coordinate of the vertical line is within the x-range of the horizontal line, and the y-coordinate of the horizontal line is within the y-range of the vertical line.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isSelfCrossing(int[] distance) {
        int n = distance.length;
        if (n <= 3) {
            return false;
        }

        List<long[]> lines = new ArrayList<>();
        long x = 0, y = 0;
        int[][] dirs = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; // N, W, S, E

        for (int i = 0; i < n; i++) {
            long prevX = x;
            long prevY = y;
            x += dirs[i % 4][0] * (long)distance[i];
            y += dirs[i % 4][1] * (long)distance[i];

            long[] newLine = {prevX, prevY, x, y};

            // Check for intersection with non-adjacent previous lines
            for (int j = 0; j < lines.size() - 1; j++) {
                if (intersects(lines.get(j), newLine)) {
                    return true;
                }
            }
            lines.add(newLine);
        }

        return false;
    }

    private boolean intersects(long[] l1, long[] l2) {
        // l1 is horizontal, l2 is vertical
        if (l1[1] == l1[3] && l2[0] == l2[2]) {
            return check(l1[0], l1[2], l2[0]) && check(l2[1], l2[3], l1[1]);
        }
        // l1 is vertical, l2 is horizontal
        if (l1[0] == l1[2] && l2[1] == l2[3]) {
            return check(l2[0], l2[2], l1[0]) && check(l1[1], l1[3], l2[1]);
        }
        return false;
    }

    private boolean check(long a, long b, long c) {
        return Math.min(a, b) <= c && c <= Math.max(a, b);
    }
}
```
### Algorithm
1. Initialize a list of line segments, `lines`, to store the path.
2. Start at `(x, y) = (0, 0)`.
3. Define the direction vectors: North `(0, 1)`, West `(-1, 0)`, South `(0, -1)`, East `(1, 0)`.
4. Iterate through the `distance` array from `i = 0` to `n-1`:
   a. Determine the current direction based on `i % 4`.
   b. Calculate the end point `(nextX, nextY)` of the new segment.
   c. The new segment is from `(x, y)` to `(nextX, nextY)`.
   d. Iterate through all previously generated segments in `lines` from index `j = 0` to `i-2` (to avoid checking adjacent segments).
   e. For each previous segment, check if it intersects with the new segment.
   f. Since all segments are either horizontal or vertical, the intersection check is straightforward:
      - A horizontal segment `(x1, y)-(x2, y)` intersects a vertical segment `(x, y1)-(x, y2)` if `min(x1, x2) <= x <= max(x1, x2)` and `min(y1, y2) <= y <= max(y1, y2)`.
   g. If an intersection is found, return `true`.
   h. Add the new segment to the `lines` list.
   i. Update the current position: `x = nextX`, `y = nextY`.
5. If the loop completes without finding any intersections, return `false`.

## Linear Time, Constant Space Geometric Analysis
A much more efficient approach is to recognize that a self-crossing is a local event. The path has a spiral-like structure, either expanding or contracting. A crossing can only occur when this structure is violated in specific ways. By analyzing the relative lengths of the last six segments, we can determine if the current move will cause a crossing. This allows us to solve the problem in a single pass with constant memory.
**Time:** O(N), where N is the length of the `distance` array. We perform a single pass through the array, and each step involves a constant number of comparisons. · **Space:** O(1). We only need to access a fixed number of previous elements from the input array at any given time.
**Pros:** Extremely efficient with linear time complexity.; Requires only constant extra space, making it suitable for very large inputs.
**Cons:** The logic is complex and the derivation of the geometric conditions is not trivial.; It's easy to make mistakes with the indices and inequalities in the conditions.
### Explanation
Instead of a full simulation, we can use geometric insights. The path won't cross itself if it's always spiraling outwards (e.g., `distance[i] > distance[i-2]` for all `i >= 2`) or always spiraling inwards. A crossing happens when the spiral changes its behavior, for example, by starting to shrink after expanding, or vice-versa.

We only need to check for three scenarios that cover all possible ways a crossing can occur. We iterate through the path from the fourth segment (`i=3`) onwards, as a crossing requires at least four segments.

- **Case 1:** The current segment `i` crosses segment `i-3`. This typically happens when an expanding spiral begins to contract. For example, the 4th segment (going East) crosses the 1st segment (going North).
- **Case 2:** The current segment `i` becomes collinear with segment `i-4` and is long enough to cross the line of segment `i-2`. This happens when, for example, `distance[i-1] == distance[i-3]`, which aligns the start of segment `i` with segment `i-4`.
- **Case 3:** The path spirals in such a way that segment `i` gets trapped within a box formed by segments `i-1` through `i-5`, forcing it to cross segment `i-5`.

By checking these three conditions at each step, we can detect any crossing in constant time per step.

```java
class Solution {
    public boolean isSelfCrossing(int[] distance) {
        int n = distance.length;
        if (n <= 3) {
            return false;
        }

        for (int i = 3; i < n; i++) {
            // Case 1: 4th line crosses 1st line
            if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3]) {
                return true;
            }

            // Case 2: 5th line meets 1st line
            if (i >= 4 && distance[i - 1] == distance[i - 3] && distance[i] + distance[i - 4] >= distance[i - 2]) {
                return true;
            }

            // Case 3: 6th line meets 1st line
            if (i >= 5 && distance[i - 2] >= distance[i - 4] && distance[i - 3] >= distance[i - 1]
                    && distance[i - 1] + distance[i - 5] >= distance[i - 3]
                    && distance[i] + distance[i - 4] >= distance[i - 2]) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
1. The path can only cross itself in a limited number of ways due to its spiral nature.
2. Any crossing must involve the current line segment and one of the few most recent segments. A crossing with a much older segment would imply a crossing with a more recent one first.
3. We can iterate through the `distance` array once, and at each step `i`, check for three specific geometric crossing patterns involving the last 6 segments (`i` to `i-5`).
4. Let `d` be the `distance` array. Iterate from `i = 3` to `n-1`:
   - **Case 1: Fourth segment crosses first.** The `i`-th segment crosses the `(i-3)`-th. This happens when the spiral shrinks. Condition: `d[i] >= d[i-2]` and `d[i-1] <= d[i-3]`.
   - **Case 2: Fifth segment crosses first.** The `i`-th segment becomes collinear with the `(i-4)`-th segment and crosses the path. This requires `i >= 4`. Condition: `d[i-1] == d[i-3]` and `d[i] + d[i-4] >= d[i-2]`.
   - **Case 3: Sixth segment crosses first.** The path gets trapped in a rectangle formed by previous segments, forcing a cross. This requires `i >= 5`. Condition: `d[i-2] >= d[i-4]`, `d[i-3] >= d[i-1]`, `d[i] + d[i-4] >= d[i-2]`, and `d[i-1] + d[i-5] >= d[i-3]`.
5. If any of these conditions are met during the iteration, return `true`.
6. If the loop finishes without any condition being met, it means no crossing occurred, so return `false`.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool IsSelfCrossing(int[] x) {
        for (var i = 3; i < x.Length; ++i) {
            if (x[i] >= x[i - 2] && x[i - 1] <= x[i - 3]) return true;
            if (i > 3 && x[i] + x[i - 4] >= x[i - 2]) {
                if (x[i - 1] == x[i - 3]) return true;
                if (i > 4 && x[i - 2] >= x[i - 4] && x[i - 1] <= x[i - 3] && x[i - 1] + x[i - 5] >= x[i - 3]) return true;
            }
        }
        return false;
    }
}
```

### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool: d = distance for i in range(3, len(d)): if d[i] >= d[i - 2] and d[i - 1] <= d[i - 3]: return True if i >= 4 and d[i - 1] == d[i - 3] and d[i] + d[i - 4] >= d[i - 2]: return True if (i >= 5 and d[i - 2] >= d[i - 4] and d[i - 1] <= d[i - 3] and d[i] >= d[i - 2] - d[i - 4] and d[i - 1] + d[i - 5] >= d[i - 3]): return True return False

```