Java Oms with explanation


  • 126
    K
    // Categorize the self-crossing scenarios, there are 3 of them: 
    // 1. Fourth line crosses first line and works for fifth line crosses second line and so on...
    // 2. Fifth line meets first line and works for the lines after
    // 3. Sixth line crosses first line and works for the lines after
    public class Solution {
        public boolean isSelfCrossing(int[] x) {
            int l = x.length;
            if(l <= 3) return false;
            
            for(int i = 3; i < l; i++){
                if(x[i] >= x[i-2] && x[i-1] <= x[i-3]) return true;  //Fourth line crosses first line and onward
                if(i >=4)
                {
                    if(x[i-1] == x[i-3] && x[i] + x[i-4] >= x[i-2]) return true; // Fifth line meets first line and onward
                }
                if(i >=5)
                {
                    if(x[i-2] - x[i-4] >= 0 && x[i] >= x[i-2] - x[i-4] && x[i-1] >= x[i-3] - x[i-5] && x[i-1] <= x[i-3]) return true;  // Sixth line crosses first line and onward
                }
            }
            return false;
        }
    }

  • 0
    E
    This post is deleted!

  • 9
    E

    Best solution so far. However, I think it would be a little bit more helpful if you could rephrase your comments somehow.

    • The first if checks if current line crosses the line 3 steps ahead of it
    • The second if checks if current line crosses the line 4 steps ahead of it
    • The third if checks if current line crosses the line 6 steps ahead of it

    If none of the above condition is satisfied, there must not be any cross.

    Other minor comment:

    • if(l <= 3) return false; is not necessary

  • 52
    E

    I really like this solution, and really brilliant solution! I go ahead and consolidated it a little bit with new comments:

    public boolean isSelfCrossing(int[] x) {
        for(int i=3, l=x.length; i<l; i++) {
            if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true;  // Case 1: current line crosses the line 3 steps ahead of it
            else if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true; // Case 2: current line crosses the line 4 steps ahead of it
            else if(i>=5 && x[i-2]>=x[i-4] && 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;  // Case 3: current line crosses the line 6 steps ahead of it
        }
        return false;
    }
    

    Here is an image that illustrates the three possible crosses:


  • 2
    K

    Nice answer, I registered on this website 7 months ago and I still write redundant codes here and there.
    Sorry I didn't respond in time.
    Actually I didn't come up with all the possible cross scenarios in the first place, I learned them from all the test cases.
    Hope to exchange ideas in the future!


  • 0
    E

    Sure. Keep up the good work~


  • 122
    N

    Base on your solution and comments, here is the images.
    So far the best solution.

    class Solution {
    public:
        bool isSelfCrossing(vector<int>& x) {
            for(int i=3, l=x.size(); i<l; i++) {
                // Case 1: current line crosses the line 3 steps ahead of it
                if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) return true;  
                // Case 2: current line crosses the line 4 steps ahead of it
                else if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2]) return true; 
                // Case 3: current line crosses the line 6 steps ahead of it
                else if(i>=5 && x[i-2]>=x[i-4] && 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;  
            }
            return false;
        }
    
    /*               i-2
        case 1 : i-1┌─┐
                    └─┼─>i
                     i-3
                     
                        i-2
        case 2 : i-1 ┌────┐
                     └─══>┘i-3
                     i  i-4      (i overlapped i-4)
    
        case 3 :    i-4
                   ┌──┐ 
                   │i<┼─┐
                i-3│ i-5│i-1
                   └────┘
                    i-2
    
    */
    };
    

  • 10

    Pretty awesome solution for a problem that tends to produce ugly code and lots of branches. One minor note: case two really makes sense only when i == 4. For i >= 5 it becomes redundant because when a line merges with the (i − 4)th line, it also crosses the (i − 5)th line right where the (i − 4)th line begins. This can allow us to reduce the number of branches in the loop, like this:

    public boolean isSelfCrossing(int[] x) {
        if (x.length >= 5 && x[1] == x[3] && x[2] - x[4] <= x[0]) { // 5th line merges with the 1st one
            return true;
        }
        for (int i = 3; i < x.length; ++i) {
            if (x[i - 1] <= x[i - 3] && x[i] >= x[i - 2] // crosses the line three steps behind
                    || i >= 5 && x[i - 2] >= x[i - 4]
                       && x[i - 3] - x[i - 1] >= 0 && x[i - 3] - x[i - 1] <= x[i - 5]
                       && x[i] >= x[i - 2] - x[i - 4]) { // crosses the line five steps behind
               return true;
           }
        }
        return false;
    }
    

  • 2

    In case 3 the current line crosses the line 5 steps ahead of it (or, rather, behind it), not 6. In case 2 the line doesn't actually cross, but merges with the line four steps behind it (and at the same time crosses the one five steps behind, if there is any, see my answer).


  • 0
    K

    Really, really fantastic, I saw the 0ms runtime and thought right there it couldn't be any more optimized, but you still came up with this idea which cuts the redundant branch!


  • 1
    K

    Nice graph there! I was lazy so I just described using words, which doesn't quitely get the point through, with your graph it's all there:)


  • 1
    H

    excellent graph, I wonder how you managed to "draw" those nice graphs using "typing"


  • 0
    M
    This post is deleted!

  • 0
    P

    It's so clear!


  • 0
    Q
    This post is deleted!

  • 2
    B

    I wanna ask why hasn't anyone considered line 7 crossing(meeting) line 1? Or is this situation covered in any of these 3 cases?


  • 0
    H

    Nice solution. But is it correct for [1,1,3,3,1,1,1]?


  • 0
    H

    I see. My bad, sorry.


  • 0
    K
    This post is deleted!

  • 1
    K

    Nice question, in fact, if line 7 meets line 1, it must cross line 2, which falls into the second category, for example[1,1,2,2,3,1,1] actually returns true in 2nd branch.


Log in to reply
 

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