Saturday, June 4, 2016

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)

I think this problem is quite "hard" to me. There are only three situations when the path will not cross itself:

  1. The number keeps increasing (which will form an growing spiral).
  2. The number keeps decreasing (which will form an shrinking spiral).
  3. The number increases first, then decreases, and never increases again.   

The harder part is to implement all three situations. Since our program should be one pass, we should check if the number keeps increasing (or decreasing), or if it changes its trend.

public boolean isSelfCrossing(int[] x) {
        if (x == null || x.length < 4)
            return false;
        int length = x.length;
        int t1 = 0, t2 = x[0], t3 = x[1], t4 = x[2], t5;
        boolean isIncrease = (t4 > t2);
        for (int i = 3; i < length; i++) {
            t5 = x[i];
            if (isIncrease && (t3 >= t5)) {
                //condition 1
                if ((t1 + t5) < t3 || ((i < length - 1) && x[i + 1] + t2 < t4))
                    isIncrease = false;
                //condition 2
                else if (i < length - 1)
                    return true;
            // condition 3
            } else if (!isIncrease && (t3 <= t5))
                return true;
            t1 = t2;
            t2 = t3;
            t3 = t4;
            t4 = t5;
        }
        return false;
    }






No comments:

Post a Comment