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)
The problem is tricky to solve. There are in total three cases to consider if there is no cross
1. Only have internal squirrels. In this case, the length of each step should go smaller and smaller. So we only need to check if x[i] < x[i - 2].
2. Only have external squirrels. In this case, the length of each step should go larger and larger. So we only need to check if x[i] > x[i - 2].
3. In the third case, it goes external squirrel first then go internal. In this case, the trick part is we may need to update the base of the internal squirrel.
Code (Java):
public class Solution { public boolean isSelfCrossing(int[] x) { if (x == null || x.length <= 3) { return false; } int i = 2; int len = x.length; // case 1: outside squrial while (i < len && x[i] > x[i - 2]) { i++; } if (i == len) { return false; } // case 2: transist to inside squrial if ((i >= 4 && x[i] + x[i - 4] >= x[i - 2]) || (i == 3 && x[i] == x[i - 2])) { x[i - 1] -= x[i - 3]; } i++; // case 3: inside squrial while (i < len && x[i] < x[i - 2]) { i++; } return i != len; } }
so smart! this solution is much more clear;-) thanks~
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThanks for understandable code.
ReplyDelete