Simple C++ 0ms Soln w/ explanation


  • 0
    T
    // There can be an inward spiral OR an outward spiral which may or may not be followed by an inward spiral
    // So the sequence with either be all decreasing OR increasing and then decreasing (only one hill)
                
    class Solution {
    public:
        bool isSelfCrossing(vector<int>& x) {
            if (x.size() <= 3) return false;
            int i=2;
            
            // Check if it starts in desending order
            if (x[2] < x[0]){
                // Confirm rest all are in decending order as well
                for(i=3; i < x.size(); i++){
                    if (x[i] >= x[i-2]) return true;
                }
                // If not then there is a overlap
                return false;
            }
            
            // Look for the place/hill (if any) where it becomes non-asending
            while(++i < x.size()) if (x[i] <= x[i-2]) break;
            
            // If not found, then there is no overlap
            if (i >= x.size()) return false;
    
    
            // Else make sure the following two conditions are not met, at that point
            // <---------------^
            // |               |
            // |               |
            // |               |
            // |               |
            // |  ------------>|
            // |     ^
            // |     |
            // v---->|
            if (i-4 >= 0 && (x[i-4] + x[i] >= x[i-2]) && (x[i+1] >= x[i-1] - x[i-3])) return true;
    
    
    
            // <---------------^
            // |               |
            // |               |
            // |               |
            // |               |
            // |               
            // |     
            // v--------------->
            if (i-3 == 0 && x[i] == x[i-2] && (x[i-1] == x[i-3] || (i+1 < x.size() && x[i+1] + x[i-3] >= x[i-1]))) return true;
            
            // Confirm rest are in decending order, another hill => overlap
            while(++i < x.size()) if (x[i] >= x[i-2]) return true;
            return false;
        }
    };
    

Log in to reply
 

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