Self Crossing

The given problem describes a scenario where you’re moving on an X-Y plane based on the given distances. You start at (0, 0), move north, west, south, and east in a cyclic manner. The task is to find out if the path crosses itself.

The scenario where crossing occurs can be broken down into a few cases:

  1. Case 1: When the 4th line crosses the 1st line (like the first example).
  2. Case 2: When the 5th line crosses the 1st line (like a pentagon with a shorter side).
  3. Case 3: When the 6th line crosses the 1st line.

We can translate these cases into conditions and check them as we iterate through the distances.

Here’s a code snippet that applies the logic:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        if len(distance) < 4:
            return False

        for i in range(3, len(distance)):
            # Case 1: Fourth line crosses the first line
            if distance[i] >= distance[i - 2] and distance[i - 1] <= distance[i - 3]:
                return True
            # Case 2: Fifth line crosses the first line
            if i >= 4 and distance[i - 1] == distance[i - 3] and distance[i] + distance[i - 4] >= distance[i - 2]:
                return True
            # Case 3: Sixth line crosses the first line
            if i >= 5 and 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

Key Takeaways

  • The problem can be solved by carefully analyzing the conditions that lead to self-crossing.
  • The above code snippet efficiently checks for these conditions, using constant space and linear time.
  • The time complexity of this solution is (O(n)), and the space complexity is (O(1)), where (n) is the length of the distance array.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def isSelfCrossing(self, x: List[int]) -> bool:
        l = len(x)
        if l <= 3:
            return False

        for i in range(3, l):
            if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:
                return True  # Fourth line crosses first line and onward
            if i >= 4:
                if x[i - 1] == x[i - 3] and x[i] + x[i - 4] >= x[i - 2]:
                    return True  # Fifth line meets first line and onward
            if i >= 5:
                if x[i - 2] - x[i - 4] >= 0 and x[i] >= x[i - 2] - x[i - 4] and x[i - 1] >= x[i - 3] - x[i - 5] and x[i - 1] <= x[i - 3]:
                    return True  # Sixth line crosses first line and onward

        return False

Identifying Problem Isomorphism

“Self Crossing” can be mapped to “Robot Bounded In Circle”.

“Self Crossing” involves a person moving in a plane along a given path. The task is to determine if the path of the person crosses itself at any point. This requires processing a series of steps and keeping track of the path traversed to check for intersections.

In “Robot Bounded In Circle”, there is a robot moving in a plane according to certain instructions. The goal is to determine if the final position of the robot after executing the instructions is in a bounded circle. This involves processing a series of steps and keeping track of the robot’s position and direction at each step.

The reason is that both problems deal with tracking movements in a plane and checking for a certain condition (self-crossing or remaining within a circle). However, the “Self Crossing” problem is more complex as it requires checking for intersections with any part of the path, while the “Robot Bounded In Circle” problem only checks if the robot’s movements are constrained within a certain area.

10 Prerequisite LeetCode Problems

“335. Self Crossing” deals with array manipulation and conditional checks within a complex pattern. Here are 10 problems to prepare for it:

  1. “283. Move Zeroes” - Basic problem for learning how to manipulate elements in an array.

  2. “485. Max Consecutive Ones” - Simple problem to get used to array iteration and conditions.

  3. “88. Merge Sorted Array” - A bit more complex manipulation with two arrays.

  4. “75. Sort Colors” - This problem makes you handle three possible values, and not just two.

  5. “448. Find All Numbers Disappeared in an Array” - More complex manipulation and a bit more complex conditions.

  6. “41. First Missing Positive” - It has a tricky part that is similar to the idea of cycles in arrays.

  7. “152. Maximum Product Subarray” - This problem introduces you to the idea of keeping track of multiple possible outcomes.

  8. “769. Max Chunks To Make Sorted” - This problem could help you to better understand how to divide the array based on the conditions inside it.

  9. “287. Find the Duplicate Number” - Complex problem about cycles in the array, but the conditions are simpler than in problem 335.

  10. “189. Rotate Array” - A more complex problem about handling the elements of the array in a cyclic way.

This list includes problems of increasing complexity, starting with basic array manipulations and ending with complex conditions and manipulations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
  def isSelfCrossing(self, x: List[int]) -> bool:
    if len(x) <= 3:
      return False

    for i in range(3, len(x)):

      if x[i - 2] <= x[i] and x[i - 1] <= x[i - 3]:
        return True

      if i >= 4 and x[i - 1] == x[i - 3] and x[i - 2] <= x[i] + x[i - 4]:
        return True

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

    return False

Problem Classification

Self Crossing - This problem asks to check if a moving line on a grid crosses itself. This is a Movement Tracking Problem.

Language Agnostic Coding Drills

  1. Length Check: The initial step is checking whether the length of the array is less than or equal to 3. If so, the function should return false immediately. This serves as an edge-case handler for the algorithm.

  2. Loop Through Elements: This solution utilizes a for loop that begins from the third index (i.e., i = 3) up to the last index of the array x. This is to perform checks on each item and its neighboring items.

  3. Crossing Checks: The subsequent three steps involve specific checks to determine whether a path crosses itself. Here are the three conditions, in order of complexity:

    • Check if the current step is equal to or larger than the step two steps before, and if the step immediately before is equal to or smaller than the step three steps before. If this is true, return true.
    • If i >= 4 (meaning we’re at least four steps in), check if the previous step is equal to the step three steps before and if the step two steps before is equal to or smaller than the current step plus the step four steps before. If this condition is met, return true.
    • If i >= 5 (meaning we’re at least five steps in), check a set of conditions: if the step four steps before is equal to or smaller than the step two steps before, and if the step two steps before is equal to or smaller than the current step plus the step four steps before, and if the previous step is equal to or smaller than the step three steps before, and if the step three steps before is equal to or smaller than the previous step plus the step five steps before. If all these conditions are met, return true.

  4. Return False: If none of the above conditions are met after checking all items in the array, the function should return false.

To implement the final solution:

  • First, master how to check the length of an array and return a value based on the length.
  • Second, learn how to traverse arrays in a loop and access the elements at different indices.
  • Third, learn how to implement complex logical conditions with multiple parts and comparisons.
  • Lastly, learn how to return a default value if no conditions in a set of checks are met.

By tackling these drills individually and then combining them, you can understand the original solution better and apply these concepts to similar problems.

Targeted Drills in Python

  1. Length Check:
1
2
3

nums = [1, 2, 3, 4]
if len(nums) <= 3:
    print(False)
  1. Loop Through Elements:
1
2
3

nums = [1, 2, 3, 4, 5]
for i in range(3, len(nums)):
    print(nums[i])
  1. Crossing Checks:

Here are the three conditions, in order of complexity:

  • Check if the current step is equal to or larger than the step two steps before, and if the step immediately before is equal to or smaller than the step three steps before.
1
2
3
4

nums = [1, 3, 2, 1, 5]
for i in range(3, len(nums)):
    if nums[i - 2] <= nums[i] and nums[i - 1] <= nums[i - 3]:
        print(True)
  • If i >= 4 (meaning we’re at least four steps in), check if the previous step is equal to the step three steps before and if the step two steps before is equal to or smaller than the current step plus the step four steps before.
1
2
3
4

nums = [1, 3, 2, 1, 5, 6]
for i in range(4, len(nums)):
    if nums[i - 1] == nums[i - 3] and nums[i - 2] <= nums[i] + nums[i - 4]:
        print(True)
  • If i >= 5 (meaning we’re at least five steps in), check a set of conditions.
1
2
3
4
5

nums = [1, 3, 2, 1, 5, 6, 7]
for i in range(5, len(nums)):
    if (nums[i - 4] <= nums[i - 2] and nums[i - 2] <= nums[i] + nums[i - 4] and 
    nums[i - 1] <= nums[i - 3] and nums[i - 3] <= nums[i - 1] + nums[i - 5]):
        print(True)
  1. Return False:
1
2
3
4
5
6
7
8
9

nums = [1, 3, 2, 1, 5, 6, 7]
found = False
for i in range(5, len(nums)):
    if (nums[i - 4] <= nums[i - 2] and nums[i - 2] <= nums[i] + nums[i - 4] and 
    nums[i - 1] <= nums[i - 3] and nums[i - 3] <= nums[i - 1] + nums[i - 5]):
        found = True
        break
if not found:
    print(False)

These drills target different aspects of the original problem. By combining all these drills, one can recreate the original solution.