Python Solution


  • 0
    M

    Algorithm
    If there are less than 4 elements, then there is no chance to cross, return False.
    We then compare the second and fourth edges (l1 and l3).
    If l1 < l3 (grow outwards)
    For each edge i starting from index 0, if each x[i] < x[i+2], we keep adding i until n-2 is reached. However, if in the middle of it, we find x[i] >= x[i+2], we need to consider a special case where x[i+2] + x[i-2] >= x[i] and x[i+3] + x[i-1] >= x[i+1].
    If this case does not happen, we simply start recursion from current i, which will address the case of first growing outwards, then growing inwards.
    If l1 > l3 (grow inwards)
    For each edge i starting from index 1, if x[i] > x[i+2], we keep increase i until n-2 is reached. If anything else happens, we break. So if last i < n-2, we say there is crossing, otherwise, there is no crossing.
    If l1 == l3 (boundary case)
    There are three cases.
    If x[i] >= x[i+2], then there is crossing.
    If x[i] < x[i+2], we need to increase i by 2, then consider:

    1. i+2 is greater than n-1; no crossing
    2. x[i+2] + x[i-2] >= x[i]; crossing

    Code

    class Solution(object):
        def isSelfCrossing(self, x):
            """
            :type x: List[int]
            :rtype: bool
            """
            n = len(x)
            if n < 4:
                return False
            
            if x[1] < x[3]:
                i = 0
                while i < n-2:
                    if x[i] < x[i+2]:
                        i += 1
                    else:
                        if x[i+2] + x[i-2] >= x[i] and x[i+3] + x[i-1] >= x[i+1]:
                            break
                        return self.isSelfCrossing(x[i::])
            elif x[1] > x[3]:
                i = 1
                while i < n-2:
                    if x[i] > x[i+2]:
                        i += 1
                    else:
                        break
            else:
                i = 0
                while i < n-2:
                    if x[i] >= x[i+2]:
                        break
                    else:
                        i += 2
                        if i + 2 > n-1:
                            return False
                        if x[i+2] + x[i-2] >= x[i]:
                            break
            if i >= n-2:
                return False
            else:
                return True 
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.