Self Crossing

Hard
1310.

Self Crossing

Self Crossing is a hard coding problem on arrays, math and geometry, asked in Amazon and Google interviews.

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^5
  • 1 <= distance[i] <= 10^5

Follow-up: Can you do it in one pass with O(1) extra space?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} distance
 * @return {boolean}
 */
var isSelfCrossing = function(distance) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= distance[i] <= 10^5

Follow-up: Can you do it in one pass with O(1) extra space?

Hints for Self Crossing

  1. Hint 1

    A leg can only hit legs that are 3, 4 or 5 steps older; anything older is shielded by those.

  2. Hint 2

    Leg i hits leg i - 3 when it is at least as long as leg i - 2 while leg i - 1 is no longer than leg i - 3.

  3. Hint 3

    Leg i meets leg i - 4 when leg i - 1 exactly equals leg i - 3 and legs i and i - 4 together reach leg i - 2; leg i hits leg i - 5 in 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

  1. For each i >= 3, let d = distance.
  2. Case 1 (meets leg i-3): d[i] >= d[i-2] and d[i-1] <= d[i-3].
  3. Case 2 (meets leg i-4 head-on): i >= 4, d[i-1] == d[i-3] and d[i] + d[i-4] >= d[i-2].
  4. 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] and d[i-1] + d[i-5] >= d[i-3].
  5. Return true at the first case that holds; false if 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 False

Java

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