C code, 0ms, one-pass algorithm with O(1) extra space


  • 0
    1

    thx for @district10

    there is only 3 cases of self crossing
    //  1) 4 lines
    //         #       
    //       <---[2]----+        [2]: second failure
    //         |        |
    //         |       [1]       [1]: first  failure
    //         |        |
    //         +--------+
    //  2) 5 lines;
    //         +-------+
    //         |       |
    //         |       #
    //         |
    //         |       ^
    //         |       |
    //         +-------+
    //  2) 6 lines
    //      +----+
    //      |    |
    //      |  <----[2]----^     [2]: second failure
    //      |    #         |
    //      |             [1]    [1]: first  failure
    //      |              |
    //      +--------------+
    
    bool isSelfCrossing(int* x, int xSize) {
        for (int i=3; i<xSize; ++i) {
            if (/*(i>=3) && */(x[i]>=x[i-2]) && (x[i-1]<=x[i-3])) return true;   // 4 lines
            else if ((i>=4) && (x[i-1]==x[i-3]) && ((x[i]+x[i-4])>=x[i-2])) return true; // 5 lines
            else if ((i>=5) && (x[i-2]>x[i-4]) && (x[i-3]>x[i-5]) && (x[i]+x[i-4]>=x[i-2]) && (x[i-1]<=x[i-3])&&(x[i-1]+x[i-5]>=x[i-3])) return true;  // 6 lines
        }
        return false;
    }```

Log in to reply
 

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