335. Self Crossing

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.

Solution

public class Solution {

    public boolean isSelfCrossing(int[] x) {
        if (x == null || x.length == 0) return false;
        Set<String> set = new HashSet<>();
        set.add(new Point(0,0).toString());

        int direction = 0;
        int m = 0;
        int n = 0;
        for(int i = 0; i < x.length; i ++) {
            int currentValue = x[i];

            while (currentValue > 0) {
                switch (direction) {
                    case 0:
                        n++;
                        break;
                    case 1:
                        m--;
                        break;
                    case 2:
                        n--;
                        break;
                    case 3:
                        m++;
                        break;
                }

                Point current = new Point(m,n);
                if (set.contains(current.toString())) {
                    return true;
                } else {
                    set.add(current.toString());
                }
                currentValue --;
            }

            direction++;
            direction = direction% 4;
        }

        return false;
    }

    public class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return x+","+y;
        }
    }
}