Leetcode Self Crossing problem solution

YASH PAL,

In this Leetcode Self Crossing problem solution, You are given an array of integers distance.

You start at point (0,0) on an X-Y plane and you move distance[0] meters to the north, then distance[1] meters to the west, distance[2] meters to the south, distance[3] meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise. Return true if your path crosses itself, and false if it does not.

Leetcode Self Crossing problem solution

Problem solution in Python.

class Solution:
    def isSelfCrossing(self, x):
        """
        :type x: List[int]
        :rtype: bool
        """
        if len(x) < 4:
            return False
        x.append(0)
        x.append(0)
        for i in range(2,len(x)-2):
            if x[i] <= x[i-2]:
                tmp = x[i-2] - x[i-4]
                if tmp > 0:
                    if x[i]>=tmp:
                        if x[i+1] != 0 and x[i+1] >= x[i-1]-x[i-3]:
                            return True
                    else:
                        if x[i+1] >= x[i-1]:
                            return True
                else:
                    if x[i+1] >= x[i-1]:
                        return True
        return False

Problem solution in Java.

public boolean isSelfCrossingExpand(int[] x, int start){
        for (int i=start;i x[i-2]){
                continue;
            } else {
                int bar = (i>=4) ? x[i-4] : 0;
                if (x[i] <= x[i-2] && x[i] >= (x[i-2] - bar)){
                    if ( i+1 == x.length){
                        return false;
                    }
                    if (x[i+1] >= (x[i-1] - x[i-3])){
                        return true;
                    }
                    return isSelfCrossingShrink(x,i+2);
                } else {
                    return isSelfCrossingShrink(x,i+1);
                }
            }        
        }
        return false;
    }

    public boolean isSelfCrossingShrink(int[] x, int start){
        for (int i=start; i= x[i-2])
                return true;
        }
        return false;
    }
    
    public boolean isSelfCrossing(int[] x) {
        if (x.length<=3) return false;

        if (x[2] <= x[0]) return isSelfCrossingShrink(x,3);        
        return isSelfCrossingExpand(x,3);
        
    }
}

Problem solution in C++.

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        
        if(x.size() < 4)
            return false;
        
        for(int i = 3; i < x.size(); i++) {
            if(x[i] >= x[i-2] and x[i-1] <= x[i-3])
                return true;
            if(i >= 4) {
                if(x[i-1] == x[i-3] and x[i] >= x[i-2]-x[i-4])
                    return true;
            }
            if(i >= 5) {
                if(x[i-2]-x[i-4] >= 0 and x[i] >= x[i-2]-x[i-4] and
                   x[i-1] >= x[i-3]-x[i-5] and x[i-1] <= x[i-3]) 
                    return true;
            }
        }
        return false;
    }
};

Problem solution in C.

bool isSelfCrossing(int* x, int xSize) {

int i;
for (i = 2; i < xSize && x[i] > x[i-2]; i++);
 
if ((++i < xSize) && ((i > 4 && x[i-1]+x[i-5]>=x[i-3]) || (i==4 && x[i-1]==x[i-3])) && x[i]+x[i-4] >= x[i-2]) return true;

for (; i < xSize && x[i] < x[i-2]; i++);

return (i < xSize);
}

coding problems solutions