Tuesday, June 7, 2016

Leetcode: 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)
Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.
Understand the problem:
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;
    }
}



3 comments: