Self Crossing - Practice Coding Problems

Self Crossing - 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.

In other words, after each move, your direction changes counter-clockwise. The directions cycle as: North → West → South → East → North...

Return true if your path crosses itself, or false if it does not.

Input & Output

Example 1 — Basic Crossing

$ Input: distance = [2,1,1,2]

› Output: true

💡 Note: Starting at (0,0): North 2→(0,2), West 1→(-1,2), South 1→(-1,1), East 2→(1,1). The fourth line (East) crosses the first line (North).

Example 2 — No Crossing

$ Input: distance = [1,2,3,4]

› Output: false

💡 Note: The path forms an expanding spiral. Starting at (0,0): North 1→(0,1), West 2→(-2,1), South 3→(-2,-2), East 4→(2,-2). No lines intersect.

Example 3 — Simple Square

$ Input: distance = [1,1,1,1]

› Output: true

💡 Note: Forms a perfect 1×1 square: North→(0,1), West→(-1,1), South→(-1,0), East→(0,0). The fourth line ends exactly at the starting point.

Constraints

1 ≤ distance.length ≤ 10⁵
1 ≤ distance[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of distances [2,1,1,2] for N,W,S,E moves

Path Generation

Draw lines counter-clockwise from (0,0)

Crossing Check

Detect if any lines intersect

Key Takeaway

🎯 Key Insight: Due to counter-clockwise movement, a line can only intersect with one of the previous 3 lines, enabling O(n) pattern recognition.

Asked in

G Google 25 a Amazon 18

The key insight is recognizing that in a counter-clockwise movement pattern, a line can only cross with one of the three most recent previous lines. The optimal approach uses pattern recognition to detect specific geometric crossing conditions in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Pattern Recognition	O(n)	O(1)	Use geometric patterns to detect crossing with only recent segments
Brute Force - Check All Line Intersections	O(n²)	O(n)	Store all line segments and check every pair for intersection

Optimized Pattern Recognition — Algorithm Steps

Track only the last 4-6 line lengths
Check three specific crossing patterns
Return true if any pattern matches crossing conditions

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Recent Lines

Keep track of last few line lengths

Check Patterns

Test specific geometric crossing conditions

Early Detection

Return true when crossing pattern found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* distance, int n) {
    if (n < 4) {
        return false;
    }
    
    for (int i = 3; i < n; i++) {
        // Fourth line crosses first line
        if (distance[i] >= distance[i-2] && 
            distance[i-1] <= distance[i-3]) {
            return true;
        }
            
        // Check for fifth line crossing second line
        if (i >= 4) {
            if (distance[i-1] <= distance[i-3] &&
                distance[i-3] <= distance[i-1] + distance[i-5] &&
                distance[i-2] <= distance[i-4] &&
                distance[i-4] <= distance[i-2] + distance[i] &&
                distance[i] >= distance[i-2] - distance[i-4] &&
                distance[i-1] >= distance[i-3] - distance[i-5]) {
                return true;
            }
        }
                
        // Check for sixth line crossing third line  
        if (i >= 5) {
            if (distance[i-2] <= distance[i-4] &&
                distance[i-3] <= distance[i-1] &&
                distance[i-1] <= distance[i-3] + distance[i-5] &&
                distance[i] <= distance[i-2] + distance[i-4]) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array
    int distance[1000];
    int size = 0;
    
    char* ptr = line + 1; // Skip '['
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        distance[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf(solution(distance, size) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the distance array, constant work per iteration

✓ Linear Growth

Space Complexity

O(1)

Only store a few recent distance values, no additional data structures

✓ Linear Space

67.5K Views

Medium Frequency

~45 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Pattern Recognition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler