Skip to content

335. Self Crossing 👎

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  bool isSelfCrossing(vector<int>& x) {
    if (x.size() <= 3)
      return false;

    for (int i = 3; i < x.size(); ++i) {
      if (x[i - 2] <= x[i] && x[i - 1] <= x[i - 3])
        return true;
      if (i >= 4 && x[i - 1] == x[i - 3] && x[i - 2] <= x[i] + x[i - 4])
        return true;
      if (i >= 5 && x[i - 4] <= x[i - 2] && x[i - 2] <= x[i] + x[i - 4] &&
          x[i - 1] <= x[i - 3] && x[i - 3] <= x[i - 1] + x[i - 5])
        return true;
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public boolean isSelfCrossing(int[] x) {
    if (x.length <= 3)
      return false;

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

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def isSelfCrossing(self, x: list[int]) -> bool:
    if len(x) <= 3:
      return False

    for i in range(3, len(x)):
      if x[i - 2] <= x[i] and x[i - 1] <= x[i - 3]:
        return True
      if i >= 4 and x[i - 1] == x[i - 3] and x[i - 2] <= x[i] + x[i - 4]:
        return True
      if i >= 5 and x[i - 4] <= x[i - 2] and x[i - 2] <= x[i] + x[i - 4] and x[i - 1] <= x[i - 3] and x[i - 3] <= x[i - 1] + x[i - 5]:
        return True

    return False