Javascript O(N) Time and O(1) Space Solution with explanation


  • 0
    H
      //Time is O(N) or O(4N) with 4 for loops.
      //1st loop will find the min or the left side value of where the order isn't ascending.
      //2nd loop will find the max or the right side value of where the order isn't ascending.
      //3rd loop will loop over to find the iteration where the min value occurs.
      //4th loop will loop over to find the iteration where the max value occurs.
      //The answer is iteration of max value minus the iteration of left + 1.
    
    var findUnsortedSubarray = function(nums) {
        var min = Number.MAX_SAFE_INTEGER, max = Number.MIN_SAFE_INTEGER, marker = false;
    
    
        for (var i = 1; i < nums.length; i++){
            if (nums[i] < nums[i-1]) {             //checks if a number isn't ascending
                marker = true;
            }
            if (marker) {
                min = Math.min(min,nums[i]);
            }
        }
        marker =  false;
        for (i = nums.length-2; i >= 0; i--){
            if (nums[i] > nums[i+1]){              //checks if a number isn't ascending
                marker = true;
            }
            if (marker){
                max = Math.max(max,nums[i]);
            }
        }
        var l, r;
        for (l = 0; l < nums.length; l++){
            if (min < nums[l]){
                break;
            }
        }
        for (r = nums.length-1; r >= 0; r--){
            if (max > nums[r]){
                break;
            }
        }
        return r-1 < 0 ? 0 : r-l+1;
    };

Log in to reply
 

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