Scale Engineer

Self Crossing

Hard
#0322Time: O(N^2), where N is the length of the `distance` array. For each of the N segments, we iterate through up to O(N) previous segments to check for intersections. The intersection check itself is O(1).Space: O(N), where N is the length of the `distance` array. We need to store the coordinates of all N line segments.1 company
Patterns
MathGeometry
Data structures
Array
Companies
Zomato

Prompt

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.

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

 

Example 1:

Input: distance = [2,1,1,2]
Output: true
Explanation: The path crosses itself at the point (0, 1).

Example 2:

Input: distance = [1,2,3,4]
Output: false
Explanation: The path does not cross itself at any point.

Example 3:

Input: distance = [1,1,1,2,1]
Output: true
Explanation: The path crosses itself at the point (0, 0).

 

Constraints:

  • 1 <= distance.length <= 105
  • 1 <= distance[i] <= 105

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the path-drawing process step by step. For each new line segment being drawn, we check if it intersects with any of the previous non-adjacent segments. If an intersection is found at any point, we can immediately conclude that the path crosses itself.

Algorithm

  1. Initialize a list of line segments, lines, to store the path.
  2. Start at (x, y) = (0, 0).
  3. Define the direction vectors: North (0, 1), West (-1, 0), South (0, -1), East (1, 0).
  4. Iterate through the distance array from i = 0 to n-1: a. Determine the current direction based on i % 4. b. Calculate the end point (nextX, nextY) of the new segment. c. The new segment is from (x, y) to (nextX, nextY). d. Iterate through all previously generated segments in lines from index j = 0 to i-2 (to avoid checking adjacent segments). e. For each previous segment, check if it intersects with the new segment. f. Since all segments are either horizontal or vertical, the intersection check is straightforward:
    • A horizontal segment (x1, y)-(x2, y) intersects a vertical segment (x, y1)-(x, y2) if min(x1, x2) <= x <= max(x1, x2) and min(y1, y2) <= y <= max(y1, y2). g. If an intersection is found, return true. h. Add the new segment to the lines list. i. Update the current position: x = nextX, y = nextY.
  5. If the loop completes without finding any intersections, return false.

Walkthrough

The core idea is to maintain a list of all line segments that constitute the path. As we generate each new segment based on the distance array, we perform an intersection test against all segments already in our list, except for the one immediately preceding it (as adjacent segments naturally touch at a vertex, which isn't considered a crossing unless they overlap).

Since the path consists only of North, West, South, and East movements, all segments are either perfectly horizontal or vertical. This simplifies the intersection check between two segments. A horizontal segment and a vertical segment cross if the x-coordinate of the vertical line is within the x-range of the horizontal line, and the y-coordinate of the horizontal line is within the y-range of the vertical line.

import java.util.ArrayList;import java.util.List; class Solution {    public boolean isSelfCrossing(int[] distance) {        int n = distance.length;        if (n <= 3) {            return false;        }         List<long[]> lines = new ArrayList<>();        long x = 0, y = 0;        int[][] dirs = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; // N, W, S, E         for (int i = 0; i < n; i++) {            long prevX = x;            long prevY = y;            x += dirs[i % 4][0] * (long)distance[i];            y += dirs[i % 4][1] * (long)distance[i];             long[] newLine = {prevX, prevY, x, y};             // Check for intersection with non-adjacent previous lines            for (int j = 0; j < lines.size() - 1; j++) {                if (intersects(lines.get(j), newLine)) {                    return true;                }            }            lines.add(newLine);        }         return false;    }     private boolean intersects(long[] l1, long[] l2) {        // l1 is horizontal, l2 is vertical        if (l1[1] == l1[3] && l2[0] == l2[2]) {            return check(l1[0], l1[2], l2[0]) && check(l2[1], l2[3], l1[1]);        }        // l1 is vertical, l2 is horizontal        if (l1[0] == l1[2] && l2[1] == l2[3]) {            return check(l2[0], l2[2], l1[0]) && check(l1[1], l1[3], l2[1]);        }        return false;    }     private boolean check(long a, long b, long c) {        return Math.min(a, b) <= c && c <= Math.max(a, b);    }}

Complexity

Time

O(N^2), where N is the length of the `distance` array. For each of the N segments, we iterate through up to O(N) previous segments to check for intersections. The intersection check itself is O(1).

Space

O(N), where N is the length of the `distance` array. We need to store the coordinates of all N line segments.

Trade-offs

Pros

  • Conceptually simple and easy to follow.

  • Directly models the problem statement.

Cons

  • Highly inefficient due to the nested loop structure.

  • The space requirement grows linearly with the input size.

  • Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for large inputs.

Solutions

public class Solution {    public bool IsSelfCrossing(int[] x) {        for (var i = 3; i < x.Length; ++i) {            if (x[i] >= x[i - 2] && x[i - 1] <= x[i - 3]) return true;            if (i > 3 && x[i] + x[i - 4] >= x[i - 2]) {                if (x[i - 1] == x[i - 3]) return true;                if (i > 4 && x[i - 2] >= x[i - 4] && x[i - 1] <= x[i - 3] && x[i - 1] + x[i - 5] >= x[i - 3]) return true;            }        }        return false;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem