LeetCode 335: Self Crossing

ArrayMathGeometry

Problem Description

Explanation:

To solve this problem, we need to keep track of the boundary lines that the path can cross. We define four cases where a self-crossing can happen based on the distances moved. By checking these cases, we can determine if a self-crossing occurs.

  1. The current line crosses the line 3 steps ahead.
  2. The current line crosses the line 4 steps ahead.
  3. The current line crosses the line 5 steps ahead.
  4. The current line crosses the line 6 steps ahead.

We iterate through the array of distances, keeping track of the current location and the previous locations to determine if a self-crossing occurs.

  • Time complexity: O(n) where n is the length of the input array distance.
  • Space complexity: O(1)

Solutions

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

Loading editor...