We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Self Crossing

Number: 335

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an array of integers "distance", simulate a movement starting from (0, 0) on the X-Y plane. You first move distance[0] meters north, then distance[1] meters west, distance[2] meters south, distance[3] meters east, and so on with the direction changing counter-clockwise after each move. Determine whether the constructed path crosses itself.

Key Insights

  • The movement directions follow a fixed cyclic order: North, West, South, East, then repeating.
  • Self-crossing can occur due to overlapping segments when the current line segment intersects with a segment drawn three or four moves earlier.
  • There are three primary cases to check:
    1. Current segment crosses the segment 3 moves back.
    2. Current segment touches the segment 4 moves back.
    3. Complex overlapping when the current segment crosses the segment 6 moves back.
  • The solution leverages iterative conditions to check for these specific cases without needing simulation of the entire geometry.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the distance array.
Space Complexity: O(1) since only a fixed number of variables are used.

Solution

The solution iterates through the distance array starting from the fourth value (index 3) and checks for the three crossing cases using relative segment lengths:

  1. Case 1: For i ≥ 3, check if distance[i] >= distance[i-2] and distance[i-1] <= distance[i-3].
  2. Case 2: For i ≥ 4, check if distance[i-1] == distance[i-3] and distance[i] + distance[i-4] >= distance[i-2].
  3. Case 3: For i ≥ 5, check if distance[i-2] >= distance[i-4] and distance[i] >= distance[i-2] - distance[i-4] and distance[i-1] >= distance[i-3] - distance[i-5] and distance[i-1] <= distance[i-3]. If any of these conditions hold, the path crosses itself.

The solution uses simple arithmetic comparisons, which means that no complex data structures are needed.

Code Solutions

# Python Code
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 meets the line 4 steps ahead (touching case).
            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 6 steps ahead (overlap after a bend).
            if i >= 5:
                if (distance[i - 2] >= distance[i - 4] and 
                    distance[i] >= distance[i - 2] - distance[i - 4] and 
                    distance[i - 1] >= distance[i - 3] - distance[i - 5] and 
                    distance[i - 1] <= distance[i - 3]):
                    return True
        return False

# Sample usage
sol = Solution()
print(sol.isSelfCrossing([2,1,1,2]))  # Expected output: True
← Back to All Questions