{x}
blog image

Self Crossing

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:

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

Example 2:

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

Example 3:

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

Solution Explanation for Self Crossing

This problem asks whether a path defined by a sequence of movements (north, west, south, east) crosses itself. The path starts at (0,0). The solution leverages the observation that self-crossing occurs under specific geometric conditions involving the lengths of consecutive path segments. Instead of explicitly tracking coordinates and checking for intersections, it cleverly uses the lengths to determine crossing.

Approach

The solution efficiently checks for three main scenarios that lead to self-crossing, all based on analyzing the relative magnitudes of consecutive distances:

  1. Scenario 1: d[i] >= d[i-2] and d[i-1] <= d[i-3]

    This condition checks if the current segment's length (d[i]) is greater than or equal to the length of the segment two steps back (d[i-2]), and simultaneously, the previous segment's length (d[i-1]) is less than or equal to the length of the segment three steps back (d[i-3]). This pattern guarantees a crossing. Imagine the path as a series of line segments. This condition ensures that the current segment overlaps with a previous segment, leading to a cross.

  2. Scenario 2: i >= 4 and d[i-1] == d[i-3] and d[i] + d[i-4] >= d[i-2]

    This condition handles a more complex crossing involving four or more segments. It checks if the previous segment (d[i-1]) equals the segment three steps back (d[i-3]), and if the sum of the current segment's length (d[i]) and the segment four steps back (d[i-4]) is greater than or equal to the segment two steps back (d[i-2]). This condition leads to the fourth segment crossing the second.

  3. Scenario 3: 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]

    This condition addresses a yet more complex scenario involving five or more segments. It combines multiple length comparisons to detect a specific crossing pattern. The conditions ensure that the path loops back and crosses an earlier segment.

The code iterates through the distance array, checking for these three conditions. If any of them are true, it means the path crosses itself, and the function returns True. Otherwise, if the loop completes without finding any of these conditions, it means there is no crossing, and the function returns False.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the distance array. The code iterates through the array once.

  • Space Complexity: O(1). The solution uses only a constant amount of extra space regardless of the input size. It does not use any data structures that scale with the input.

Code Explanation (Python as Example)

The Python code directly implements the three crossing conditions outlined above. The conditions are translated into concise if statements. Each if block represents one of the crossing scenarios described previously. The loop efficiently checks these conditions in a single pass. If any of them is true, the function immediately returns True, avoiding unnecessary iterations. Only if none of the crossing conditions are met after iterating through the entire array does it return False. The other languages (Java, C++, Go, C#) present the same logic, but with syntax specific to each language.