Question

Formatted question description: https://leetcode.ca/all/335.html

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 <= 10⁵
1 <= distance[i] <= 10⁵

Algorithm

In fact, there are only three cases of intersection:

     x(1)
    ┌───┐
x(2)│   │x(0)
    └───┼──>
    x(3)│

The first type is the case where the fourth side and the first side intersect. The conditions that need to be met are that the first side is greater than or equal to the third side, and the fourth side is greater than or equal to the second side. The same applies to the case where the fifth side intersects the second side, the sixth side intersects the third side, and so on, and so on.

x(1)
    ┌──────┐
    │      │x(0)
x(2)│      ^
    │      │x(4)
    └──────│
      x(3)

The second type is the case where the fifth side and the first side overlap and intersect. The conditions that need to be met are that the second side and the fourth side are equal, and the fifth side is greater than or equal to the third side and the first side. The difference is also applicable to the case where the sixth edge and the second edge overlap and intersect, and so on, and so on…

x(1)
    ┌──────┐
    │      │x(0)
x(2)│     <│────│
    │       x(5)│x(4)
    └───────────│
        x(3)

The third category is the intersection of the sixth side and the first side. The conditions that need to be met are that the fourth side is greater than or equal to the second side, the third side is greater than or equal to the fifth side, and the fifth side is greater than or equal to The difference between the third side and the first side, the sixth side is greater than or equal to the difference between the fourth side and the second side, the same applies to the intersection of the seventh side and the second side, and so on.

Code

public class Self_Crossing {

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

}

############

class Solution {
    public 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 - 1] <= d[i - 3]
                && d[i] >= d[i - 2] - d[i - 4] && d[i - 1] + d[i - 5] >= d[i - 3]) {
                return true;
            }
        }
        return false;
    }
}

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

############

class Solution(object):
  def isSelfCrossing(self, x):
    """
    :type x: List[int]
    :rtype: bool
    """
    if len(x) < 4:
      return False
    for i in range(3, len(x)):
      if x[i] >= x[i - 2] and x[i - 1] <= x[i - 3]:
        return True
      if i >= 4 and x[i - 1] == x[i - 3] and x[i] + x[i - 4] >= x[i - 2]:
        return True
      if i >= 5 and x[i - 1] <= x[i - 3] and x[i - 3] <= x[i - 1] + x[i - 5] and x[i] + x[i - 4] >= x[i - 2] and x[
        i - 4] <= x[i - 2]:
        return True
    return False

class Solution {
public:
    bool isSelfCrossing(vector<int>& distance) {
        vector<int> d = distance;
        for (int i = 3; i < 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 - 1] <= d[i - 3] && d[i] >= d[i - 2] - d[i - 4] && d[i - 1] + d[i - 5] >= d[i - 3]) return true;
        }
        return false;
    }
};

func isSelfCrossing(distance []int) bool {
	d := distance
	for i := 3; i < len(d); 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-1] <= d[i-3] && d[i] >= d[i-2]-d[i-4] && d[i-1]+d[i-5] >= d[i-3] {
			return true
		}
	}
	return false
}

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;
    }
}

335 - Self Crossing

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions