# 335. Self Crossing

You are given an array x of `n` positive numbers. You start at point `(0,0)` and moves `x[0]` metres to the north, then `x[1]` metres to the west, `x[2]` metres to the south, `x[3]` metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with `O(1)` extra space to determine, if your path crosses itself, or not.

Example 1:

``````Given _x_ = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
│

Return **true** (self crossing)
``````

Example 2:

``````Given _x_ = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>

Return **false** (not self crossing)
``````

Example 3:

``````Given _x_ = [1, 1, 1, 1],
┌───┐
│   │
└───┼>

Return **true** (self crossing)
``````

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

``````

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

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

``````class Solution {
public:
bool isSelfCrossing(vector<int>& x) {
for (int i = 3; i < x.size(); ++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;
}
};
``````

https://leetcode.com/discuss/88054/java-oms-with-explanation

https://leetcode.com/discuss/88196/re-post-2-o-n-c-0ms-solutions

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation