Self Crossing — LeetCode 335 Python Solution

The problem

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.

Example

Input

distance = [2,1,1,2]

Output

true

Explanation

The path crosses itself at the point (0, 1).

Python solution

class Solution:
    def isSelfCrossing(self, 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 - 1] <= d[i - 3]
                and d[i] >= d[i - 2] - d[i - 4]
                and d[i - 1] + d[i - 5] >= d[i - 3]
            ):
                return True
        return False

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 335. Self Crossing is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math and Geometry.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems