Self Crossing

This page explains Java solution to problem Self Crossing using Math.

Problem Statement

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.

Input: [2,1,1,2]
Output: true

Input: [1,2,3,4]
Output: false

Solution

package com.vc.hard;

class SelfCrossing {
    public boolean isSelfCrossing(int[] x) {
        if(x == null) return false;
        if(x.length <= 3) return false;

        for(int i = 3; i < x.length; i++) {
            int up = x[i - 3];
            int left = x[i - 2];
            int down = x[i - 1];
            int right = x[i];

            //Case 1: Fourth line crosses the first line
            if(up >= down && right >= left) return true;

            int upAgain = 0;
            if(i >= 4) {
                up = x[i - 4];
                left = x[i - 3];
                down = x[i - 2];
                right = x[i - 1];
                upAgain = x[i];

                //case 2: Fifth line meets first line
                if(up + upAgain >= down && left == right) return true;
            }

            int leftAgain = 0;
            if(i >= 5) {
                up = x[i - 5];
                left = x[i - 4];
                down = x[i - 3];
                right = x[i - 2];
                upAgain = x[i - 1];
                leftAgain = x[i];

                //case 3: Sixth line meets first line
                if(right >= left && leftAgain + left >= right && upAgain + up >= down && upAgain <= down) return true;
            }
        }
        return false;
    }
}

Time Complexity

O(N) Where
N is total number of elements in an input array.

Space Complexity

O(1)