Self Crossing

Problem: You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] meters to the north, then x[1] meters to the west, x[2] meters to the south, x[3] meters to the east and so on. In other words, after each move your direction changes counter-clockwise. Determine, if your path crosses itself, or not.

Example(Taken from leetcode):

┌───┐
│   │
└───┼──>
    │

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

Approach: Given the counter-clockwise restriction, there can be only following three unique cases of self crossing:

Once you understand these three conditions. The implementation is straight forward.

Implementation in C#:

        public bool IsSelfCrossing(int[] x)

        {

            if (x?.Length <= 3)

            {

                return false;

            }

            for (int i = 3; i < x.Length; ++i)

            {

                if (x[i-3] >= x[i - 1] && x[i] >= x[i - 2])

                {

                    return true;

                }

                if (i >= 4 && x[i - 4] + x[i] >= x[i - 2] && x[i - 3] == x[i - 1])

                {

                    return true;

                }

                if (i >= 5 

                    && x[i - 5] <= x[i - 3] 

                    && x[i - 4] <= x[i - 2] 

                    && x[i - 3] >= x[i - 1]

                    && x[i - 3] <= x[i - 5] + x[i - 1]

                    && x[i - 2] >= x[i]

                    && x[i - 2] <= x[i - 4] + x[i])

                {

                    return true;

                }

            }

            return false;

        }

Complexity: O(n)