LeetCode 335: Self Crossing Solution in Python – A Step-by-Step Guide

What Is LeetCode 335: Self Crossing?

In LeetCode 335: Self Crossing, you’re given an integer array distance, where distance[i] is the length of the ith move in a cyclic sequence of directions: north (i=0), west (i=1), south (i=2), east (i=3), repeating every 4 steps. Your task is to determine if the path ever crosses itself. For example, with distance = [2,1,1,2], the path crosses, returning True. This problem tests your ability to analyze geometric paths, connecting to concepts in LeetCode 149: Max Points on a Line.

Problem Statement

• Input: An integer array distance.
• Output: A boolean—True if the path crosses itself, False otherwise.
• Rules:
• Directions cycle: north, west, south, east (mod 4).
• Path starts at (0,0), moves by distance[i] in direction i%4.
• Crossing occurs if any line segments intersect (not just at endpoints).

Constraints

• 1 <= distance.length <= 10⁵
• 1 <= distance[i] <= 10⁵

Examples

• Input: [2,1,1,2]
• Output: True (North 2, West 1, South 1, East 2 crosses)
• Input: [1,2,3,4]
• Output: False (No crossing)
• Input: [1,1,1,1]
• Output: True (Square crosses at start)

Understanding the Problem: Detecting Crossings

To solve LeetCode 335: Self Crossing in Python, we need to check if a path defined by distance in cyclic directions (north, west, south, east) intersects itself. A naive approach—tracking all coordinates and checking intersections—is O(n²), too slow for 10⁵ steps. Instead, we’ll use:

• Best Solution (Pattern-Based): O(n) time, O(1) space—fast and elegant.
• Alternative Solution (Coordinate Tracking): O(n²) time, O(n) space—clear but inefficient.

Let’s start with the pattern-based solution, explained in a beginner-friendly way.

Best Solution: Pattern-Based Approach

Why This Is the Best Solution

The pattern-based approach is the top choice for LeetCode 335 because it’s efficient—O(n) time, O(1) space—and leverages geometric insights to detect crossings without storing coordinates. It checks specific length relationships between moves that could cause overlaps, focusing on three key patterns. It’s like spotting trouble spots in the dance steps—smart and quick!

How It Works

Think of this as a path-watcher:

• Step 1: Define Patterns:
• Case 1: Fourth move crosses first (e.g., i≥3: d[i] ≥ d[i-2]).
• Case 2: Fifth move crosses first (e.g., i≥4: d[i-1] ≥ d[i-3], d[i] ≥ d[i-2] - d[i-4]).
• Case 3: Sixth move crosses first (e.g., i≥5: d[i-2] = d[i-4], d[i-1] ≥ d[i-3], d[i] ≥ d[i-2]).
• Step 2: Check as You Go:
• For each move i, compare with previous moves based on index.
• Step 3: Why It Works:
• Path spirals inward or outward; crossings occur in specific length patterns.
• Only local comparisons needed, no full path tracking.

It’s like predicting overlaps with a simple rulebook!

Step-by-Step Example

Example: distance = [2,1,1,2]

• Moves: North 2, West 1, South 1, East 2
• i=0: 2 (no check)
• i=1: 1 (no check)
• i=2: 1 (no check)
• i=3: 2, d[3]=2 ≥ d[1]=1 (Case 1), True
• Result: True (East 2 crosses North 2)

Example: distance = [1,2,3,4]

• i=0: 1
• i=1: 2
• i=2: 3
• i=3: 4, 4 ≥ 2 False (no Case 1)
• Result: False (no crossing)

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        # Process each move
        for i in range(3, len(distance)):
            # Case 1: Fourth crosses first
            if distance[i] >= distance[i-2] and i >= 3:
                return True
            # Case 2: Fifth crosses first
            if (i >= 4 and distance[i-1] >= distance[i-3] and 
                distance[i] >= distance[i-2] - distance[i-4]):
                return True
            # Case 3: Sixth crosses first
            if (i >= 5 and distance[i-2] == distance[i-4] and 
                distance[i-1] >= distance[i-3] and 
                distance[i] >= distance[i-2] - distance[i-4]):
                return True

        return False  # No crossing found

• Line 3: Start at i=3 (need at least 4 moves for Case 1).
• Lines 5-6: Case 1: d[i] crosses d[i-2].
• Lines 8-9: Case 2: d[i-1] and d[i] align to cross d[i-3].
• Lines 11-13: Case 3: d[i-2] matches d[i-4], d[i-1] and d[i] cross.
• Line 15: Return False if no crossings.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(1)—no extra space.

This is like a path-crossing detective—fast and sharp!

Alternative Solution: Coordinate Tracking

Why an Alternative Approach?

The coordinate-tracking approach—O(n²) time, O(n) space—tracks all line segments by computing coordinates and checking for intersections. It’s more intuitive for visualizing the path but inefficient due to pairwise comparisons. It’s like drawing the path and checking overlaps—clear but slow!

How It Works

Track and compare:

• Step 1: Generate coordinates for each move.
• Step 2: Check all pairs of segments for intersection.
• Step 3: Return True if any cross.

Step-by-Step Example

Example: distance = [2,1,1,2]

• Coords: (0,0)-(0,2), (0,2)-(1,2), (1,2)-(1,1), (1,1)-(1,3)
• Segments:
• (0,0)-(0,2) vs (1,1)-(1,3): Cross at x=1, y=2
• Result: True

Code for Coordinate Tracking Approach

Copy codeclass Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        # Directions: north, west, south, east
        directions = [(0, 1), (-1, 0), (0, -1), (1, 0)]
        points = [(0, 0)]

        # Generate points
        for i, d in enumerate(distance):
            dx, dy = directions[i % 4]
            x, y = points[-1]
            points.append((x + dx * d, y + dy * d))

        # Check all segment pairs for intersection
        for i in range(len(points) - 1):
            for j in range(i + 2, len(points) - 1):
                x1, y1 = points[i]
                x2, y2 = points[i + 1]
                x3, y3 = points[j]
                x4, y4 = points[j + 1]

                # Check horizontal vs vertical or vice versa
                if ((x1 == x2 and x3 == x4 and min(x3, x4) <= x1 <= max(x3, x4) and 
                     min(y1, y2) <= y3 <= max(y1, y2)) or
                    (y1 == y2 and y3 == y4 and min(y3, y4) <= y1 <= max(y3, y4) and 
                     min(x1, x2) <= x3 <= max(x1, x2))):
                    return True

        return False

• Time Complexity: O(n²)—pairwise segment checks.
• Space Complexity: O(n)—points list.

It’s a path-drawing checker—vivid but heavy!

Comparing the Two Solutions

• Pattern-Based (Best):
• Pros: O(n) time, O(1) space, fast and scalable.
• Cons: Pattern logic less intuitive.
• Coordinate Tracking (Alternative):
• Pros: O(n²) time, O(n) space, clear geometry.
• Cons: Too slow for large n.

Pattern-based wins for efficiency.

Additional Examples and Edge Cases

• [1]: False.
• [1,1]: False.
• [3,3,3,3]: True.

Both handle these, but pattern-based is faster.

Complexity Breakdown

• Pattern-Based: Time O(n), Space O(1).
• Coordinate Tracking: Time O(n²), Space O(n).

Pattern-based is the clear choice.

Key Takeaways

• Pattern-Based: Spot the overlap—efficient!
• Coordinate Tracking: Draw and check—simple!
• Python: Arrays and logic shine—see [Python Basics](/python/basics).
• Paths: Patterns reveal crossings.

Final Thoughts: Detect the Overlap

LeetCode 335: Self Crossing in Python is a geometric path puzzle. The pattern-based solution offers speed and elegance, while coordinate tracking provides a tangible baseline. Want more geometric challenges? Try LeetCode 149: Max Points on a Line or LeetCode 391: Perfect Rectangle. Ready to check? Head to Solve LeetCode 335 on LeetCode (premium) and spot those crossings today!