Java O(N) O(1) 0ms solution with explanation


  • 8
    M

    There are only 3 scenarios where it won't cross itself.

    1. The distances of the moves parallel to each other keeps going up (growing spiral).
    2. The distances of the moves parallel to each other keeps going down (shrinking spiral).
    3. The distances of the moves parallel to each other first keeps going up, then keeps going down (shrinking spiral inside of the growing spiral), and never goes up.

    Our code just needs to check if there're any things violating the above rules.

    I feel there should be smarter approaches. Please reply as answer or comments. :P

    public class Solution {
        public boolean isSelfCrossing(int[] x) {
            int a1, a2, a3, a4, a5;
            
            // if it's increasing
            boolean up = false;
            
            if (x.length < 4) {
                return false;
            }
            
            a1 = 0;
            a2 = x[0];
            a3 = x[1];
            a4 = x[2];
            
            if (a2 < a4) {
                up = true;
            }
            else {
                up = false;
            }
            
            for (int i = 3; i < x.length; i++) {
                a5 = x[i];
                
                if (!up && a5 >= a3) {
                    return true;
                }
                else if (up && a5 <= a3) {
                    // succeeded in turning into decreasing
                    if (a5 + a1 < a3 || (i + 1 < x.length && x[i + 1] + a2 < a4)) {
                        up = false;
                    }
                    // not end yet
                    else if (i + 1 < x.length) {
                        return true;
                    }
                }
                
                a1 = a2;
                a2 = a3;
                a3 = a4;
                a4 = a5;
            }
            
            return false;
        }
    }

  • 0
    L

    This is really a smart idea! To check the distance between parallels makes a lot of sense! Thank you for sharing!


Log in to reply
 

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