Description
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.
Examples:
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).Solution in Python
To solve the problem of determining whether a path crosses itself while moving in a counter-clockwise direction based on the given distance array, we can analyze the movement pattern geometrically.
Key Observations:
- The path follows a consistent pattern: north, west, south, east, and then repeats.
- The path will cross itself if the current movement intersects with a previous movement.
The main challenge is to detect these intersections as we progress through the moves. Based on the pattern of movement, there are some cases where the path could cross itself:
- Case 1: The path crosses the line drawn two steps earlier.
- Case 2: The path crosses the line drawn four steps earlier.
- Case 3: The path crosses the line drawn six steps earlier.
Approach:
We can approach this problem by simulating the movement and checking if any of the conditions for self-crossing are met.
Python
class Solution:
def isSelfCrossing(self, distance: List[int]) -> bool:
# We need at least 4 moves before it's even possible to cross
for i in range(3, len(distance)):
# Case 1: Current move crosses the line two moves ago
# (i.e., the path becomes 'inward' and crosses itself)
if distance[i] >= distance[i - 2] and distance[i - 1] <= distance[i - 3]:
return True
# Case 2: Current move creates an overlap (crosses four steps earlier)
# This happens when we make a 'tight inward' turn
if i >= 4 and distance[i - 1] == distance[i - 3] and distance[i] + distance[i - 4] >= distance[i - 2]:
return True
# Case 3: A more complex overlap involving the path from six steps ago
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
# If no crossing is detected, return False
return FalseExplanation:
- Case 1:
- This checks if the current move crosses the line drawn two moves ago.
- Condition:
distance[i] >= distance[i-2]anddistance[i-1] <= distance[i-3]distance[i] >= distance[i-2]: The current move (north/south) is large enough to extend past the position two moves ago (also north/south).distance[i-1] <= distance[i-3]: The previous move (east/west) is small enough to stay within the bounds set by the move four steps ago.
- Case 2:
- This handles a situation where the current move overlaps with the path from four steps ago.
- Condition:
distance[i-1] == distance[i-3]anddistance[i] + distance[i-4] >= distance[i-2]- If the distance moved two steps earlier equals the distance moved four steps earlier, and the sum of the current and four-step-ago move is greater than or equal to the distance moved two steps ago, the path crosses.
- Case 3:
- This checks if the path crosses a more distant line from six steps ago.
- Condition:
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]
- This case ensures that even more complex crossing patterns are covered, involving several earlier moves.
Solution in C++
C++
class Solution {
public:
bool isSelfCrossing(vector<int>& distance) {
// If the distance array has less than 4 elements, it's impossible to cross itself.
if (distance.size() < 4) {
return false;
}
// Iterate through the distance array starting from the 4th element
for (int i = 3; i < distance.size(); i++) {
// Case 1: Fourth line crosses the first line (distance[i] >= distance[i-2] && distance[i-1] <= distance[i-3])
if (distance[i] >= distance[i-2] && distance[i-1] <= distance[i-3]) {
return true;
}
// Case 2: Fifth line meets the first line
// Special case: when the fifth line crosses or overlaps the first line
if (i >= 4 && distance[i-1] == distance[i-3] && distance[i] + distance[i-4] >= distance[i-2]) {
return true;
}
// Case 3: Sixth line crosses the first line
// Another special case where the sixth line crosses the first line
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;
}
}
// If no crossing was found, return false
return false;
}
};Solution in Javascript
JavaScript
var isSelfCrossing = function(distance) {
// Edge case: if the path is less than 4 moves, it can't cross itself
if (distance.length < 4) return false;
// Traverse each step after the first three since the first three steps can't form a crossing
for (let i = 3; i < distance.length; i++) {
// Case 1: The fourth move crosses the first move
// Pattern: distance[i] >= distance[i-2] and distance[i-1] <= distance[i-3]
if (distance[i] >= distance[i-2] && distance[i-1] <= distance[i-3]) {
return true;
}
// Case 2: The fifth move crosses the first move
// Pattern: distance[i-1] == distance[i-3] and distance[i] + distance[i-4] >= distance[i-2]
if (i >= 4 && distance[i-1] == distance[i-3] && distance[i] + distance[i-4] >= distance[i-2]) {
return true;
}
// Case 3: The sixth move crosses the first move
// Pattern: distance[i-2] >= distance[i-4], 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]
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;
}
}
// If no crossing is found, return false
return false;
};Solution in Java
Java
class Solution {
public boolean isSelfCrossing(int[] distance) {
// If the array has less than 4 elements, there's no way to cross itself
if (distance.length < 4) {
return false;
}
// Loop through each move starting from the 3rd move (index 3)
for (int i = 3; i < distance.length; i++) {
// Case 1: Fourth line crosses the first line (simple overlap)
if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3]) {
return true;
}
// Case 2: Fifth line meets the first line (cross from edge case)
if (i >= 4 && distance[i - 1] == distance[i - 3] && distance[i] + distance[i - 4] >= distance[i - 2]) {
return true;
}
// Case 3: Sixth line crosses the first line (complex overlap)
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;
}
}
// If no crossing detected, return false
return false;
}
}