Self Crossing — Solution in Python, Java & C++
Self Crossing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Self Crossing is a hard coding problem on arrays, math and geometry, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Math, Geometry
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A robot starts at (0, 0) and walks distance[0] units north, then distance[1] units west, then distance[2] south, distance[3] east, and so on — turning counter-clockwise by 90 degrees after every leg.
Return true if its path ever crosses or touches itself (a leg meeting any earlier part of the path other than the corner it starts from), and false otherwise.
Example 1
Input: distance = [3,2,2,3]
Output: true
Explanation: The fourth leg, heading east at y = 1, cuts through the first leg at (0, 1).
Example 2
Input: distance = [2,3,4,5,6]
Output: false
Explanation: Every leg is longer than the parallel one before it: an outward spiral never meets itself.
Example 3
Input: distance = [2,2,2,2]
Output: true
Explanation: The path returns to the origin, touching its starting point.
Constraints
1 <= distance.length <= 10^51 <= distance[i] <= 10^5
Follow-up: Can you do it in one pass with O(1) extra space?
Hints for Self Crossing
Hint 1
A leg can only hit legs that are 3, 4 or 5 steps older; anything older is shielded by those.
Hint 2
Leg
ihits legi - 3when it is at least as long as legi - 2while legi - 1is no longer than legi - 3.Hint 3
Leg
imeets legi - 4when legi - 1exactly equals legi - 3and legsiandi - 4together reach legi - 2; legihits legi - 5in the shrinking-after-growing spiral — write out that inequality too.
How to solve Self Crossing
Because the path turns the same way every time, it is a spiral that can only grow, only shrink, or grow and then shrink. A new leg can only reach the legs 3, 4 or 5 positions back, so three local inequalities decide the answer.
Approach
- For each
i >= 3, letd = distance. - Case 1 (meets leg i-3):
d[i] >= d[i-2]andd[i-1] <= d[i-3]. - Case 2 (meets leg i-4 head-on):
i >= 4,d[i-1] == d[i-3]andd[i] + d[i-4] >= d[i-2]. - Case 3 (meets leg i-5):
i >= 5,d[i-2] >= d[i-4],d[i] + d[i-4] >= d[i-2],d[i-1] <= d[i-3]andd[i-1] + d[i-5] >= d[i-3]. - Return
trueat the first case that holds;falseif none ever does.
Why it works
Leg i is parallel to legs i-2, i-4, … and perpendicular to i-1, i-3, i-5, …; it is adjacent to i-1 and can never touch i-2. While the spiral is still growing, the newest leg stays outside everything; once a leg is no longer than the one two before it, the path has turned inward and is boxed in by legs i-3 to i-5, which form the walls around it — any older leg lies outside that box. Case 1 is the inward leg running into the wall i-3; case 2 is the leg i-1 exactly retracing i-3 so leg i lands on i-4; case 3 is the transition from growing to shrinking where leg i reaches i-5. These cover every way the newest leg can touch the box.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Touching counts as crossing: every comparison uses
>=/<=, and case 2 is an exact equality. - Case 3 needs all four inequalities; dropping
d[i-2] >= d[i-4]reports crossings in shrinking spirals that never reach leg i-5. - A segment-intersection brute force is O(n²) and too slow for 10^5 legs, though it is a good way to test the formula.
Reference solution
Python
from typing import List
def isSelfCrossing(distance: List[int]) -> bool:
d = distance
for i in range(3, len(d)):
if d[i] >= d[i - 2] and d[i - 1] <= d[i - 3]:
return True
if i >= 4 and d[i - 1] == d[i - 3] and d[i] + d[i - 4] >= d[i - 2]:
return True
if (i >= 5 and d[i - 2] >= d[i - 4] and d[i] + d[i - 4] >= d[i - 2]
and d[i - 1] <= d[i - 3] and d[i - 1] + d[i - 5] >= d[i - 3]):
return True
return FalseJava
public static boolean isSelfCrossing(int[] distance) {
int[] d = distance;
for (int i = 3; i < d.length; i++) {
if (d[i] >= d[i - 2] && d[i - 1] <= d[i - 3]) return true;
if (i >= 4 && d[i - 1] == d[i - 3] && d[i] + d[i - 4] >= d[i - 2]) return true;
if (i >= 5 && d[i - 2] >= d[i - 4] && d[i] + d[i - 4] >= d[i - 2]
&& d[i - 1] <= d[i - 3] && d[i - 1] + d[i - 5] >= d[i - 3]) return true;
}
return false;
}C++
bool isSelfCrossing(vector<int>& distance) {
vector<int>& d = distance;
for (int i = 3; i < (int) d.size(); i++) {
if (d[i] >= d[i - 2] && d[i - 1] <= d[i - 3]) return true;
if (i >= 4 && d[i - 1] == d[i - 3] && d[i] + d[i - 4] >= d[i - 2]) return true;
if (i >= 5 && d[i - 2] >= d[i - 4] && d[i] + d[i - 4] >= d[i - 2]
&& d[i - 1] <= d[i - 3] && d[i - 1] + d[i - 5] >= d[i - 3]) return true;
}
return false;
}JavaScript
var isSelfCrossing = function(distance) {
var d = distance;
for (var i = 3; i < d.length; i++) {
if (d[i] >= d[i - 2] && d[i - 1] <= d[i - 3]) return true;
if (i >= 4 && d[i - 1] === d[i - 3] && d[i] + d[i - 4] >= d[i - 2]) return true;
if (i >= 5 && d[i - 2] >= d[i - 4] && d[i] + d[i - 4] >= d[i - 2] &&
d[i - 1] <= d[i - 3] && d[i - 1] + d[i - 5] >= d[i - 3]) return true;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays