Re-post: 2 O(N) C++ 0ms solutions


  • 10
    D

    The first solution is well described in KuangYuan's post and the idea is to enumerate all the self-crossing cases. Basically, there are three cases
    Case1: self-crossing is formed by the last 4 lines (like a closed rectangle)
    Case 2: self-crossing is formed by the last 5 lines (still like a closed rectangle with one edge having two moves)
    Case 3: self-crossing is formed by the last 6 lines (like two overlapped rectangles)

    class Solution {
    public:
        bool isSelfCrossing(vector<int>& x) {
            int len = x.size(),i;
            for(i=3; i<len;++i)
            {
                if(x[i]>=x[i-2] && x[i-1] <= x[i-3]) return true; // case 1, the consecutive four lines form a cross
                if(i>3 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true; // case 2, the consecutive five lines form a cross
                if(i>4 && x[i-2]>=x[i-4] && x[i-4]+x[i]>=x[i-2] && x[i-1]<=x[i-3] && x[i-5] + x[i-1]>=x[i-3]) return true;// case 3, the consecutive six lines form a cross
            }
            return false;
        }
    };
    

    The second solution is to categorize all the non-self-crossing cases: basically we can only have two valid cases: one is "grow spiral" (which means the curve expands like spiral and there is no boundaries in x and y axis) and the other is "shrink spiral" (which means the spiral curve becomes smaller and smaller and the boundaries in x and y axis are the last move in that direction). The self-crossing cases can only happen in the "shrink" case and it happens only when x[i]>=x[i-2]. The "grow" case can become a "shrink" case and that only happens when x[i]<=x[i-2]. The "shrink" case can not change to a "grow" case.
    In the solution, we use a bool grow_spiral to indicate whether the current one is a "grow spiral". if before x[i], it is a "shrink spiral", we only need to check if a self-crossing happen (i.e. x[i]>=x[i-2]); if it is a "grow spiral", we check if x[i] changes from "grow" to "shrink" (i.e. x[i]<=x[i-2]), we need to update the boundary x[i-1] (in some cases, it can be x[i-1]-x[i-3]).

    class Solution {
    public:
        bool isSelfCrossing(vector<int>& x) {
            int len = x.size(), i;
            if(len<=3) return false;
            bool grow_spiral;
    
            for(i=3, grow_spiral = x[2]>x[0]; i<len;++i)
            {
                if(!grow_spiral && x[i]>=x[i-2]) return true;//if it is a "shrink" case before x[i] and cross happens
                if(grow_spiral && x[i]<=x[i-2])
                { // if it is a grow case, and x[i] changes it to shrink
                        grow_spiral = false;
                        x[i-1] = x[i] + (i>=4?x[i-4]:0)<x[i-2]? x[i-1]:x[i-1]-x[i-3];// update boundary
                }
            }
            return false;
        }
    };
    

    My special thank goes to hohomi for pointing out one bug in Solution 2 and I believe I fixed it.


  • 0
    S

    What a great idea the solution 2. Can you please explain in detail the "update boundary" step. I am having a hard time understanding that.
    Thanks in advance.


  • 0

    The valid case you summarize is not enought, it can also be grow first and shrink secondly.


  • 0
    D

    Suppose if(grow_spiral && x[i]<=x[i-2]) will detect the grow->shrink case you mentioned, Thanks,


  • 1
    C

    Your idea is brilliant! I changed the boundary update condition, for those who also has difficulty in understanding yours.

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

  • 0

    brilliant!!!


Log in to reply
 

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