C++ O(n) solution


  • 6
    X
       int findUnsortedSubarray(vector<int>& nums) {
            int shortest = 0;
            
            int left = 0, right = nums.size() - 1;
            while (left < nums.size() - 1 && nums[left] <= nums[left + 1]) { left++; }
            while (right > 0 && nums[right] >= nums[right - 1]) { right--; };
            
            if (right > left) {
                int vmin = INT_MAX, vmax = INT_MIN;
                for (int i = left; i <= right; ++i) {
                    if (nums[i] > vmax) {
                        vmax = nums[i];
                    }
                    if (nums[i] < vmin) {
                        vmin = nums[i];
                    }
                }
                
                while (left >= 0 && nums[left] > vmin) { left--; };
                while (right < nums.size() && nums[right] < vmax) { right++; };
                
                shortest = right - left - 1;
            }
            
            return shortest;
        }
    

  • 1

    O(n) time and O(1) space, brilliant solution! Thank you.
    I made a little improvement and got 35ms beats 100%. : )

    class Solution {
    public:
        int findUnsortedSubarray(vector<int>& nums)
        {
            int n = nums.size();
            if (n <= 1) return 0;
    
            int left = 0, right = n - 1;
            while (left < n - 1 && nums[left] <= nums[left + 1]) ++left;
            if (left == n - 1) return 0; // return 0 if already sorted.
            // Or we know the array is unsorted
            // So, it's no need to judge right > 0
            while (/*right > 0 && */nums[right] >= nums[right - 1]) --right;
    
            int rmin = INT_MAX, lmax = INT_MIN;
            for (int i = left; i <= right; ++i) {
                if (nums[i] > lmax) lmax = nums[i];
                if (nums[i] < rmin) rmin = nums[i];
            }
            while (left >= 0 && nums[left] > rmin) --left;
            while (right < n && nums[right] < lmax) ++right;
            return right - left - 1;
        }
    };
    

  • 0

    You can look my O(n) solution which beats 100%: https://discuss.leetcode.com/topic/89457/c-o-n-solution-which-beats-100


  • 0
    B

    @Xnming Could you please explain your approach? After finding the location of the left and right indices, you find the lowest and the highest elements in the interval (left, right) and then again move the left and the right pointers to their respective far ends - why exactly do you do this? Could you please explain the intuition behind doing this?

    Thanks!


  • 1
    X

    @BatCoder Considering the array A [2, 3, 7, 8, 1, 5, 6], at the first pass, A[left] = 8 and A[right] = 1, but obviously 8 is the largest element in the array and 1 is the smallest one. We need to move 'left' to the first element that less than 1 and move 'right' to the first element that bigger than 8, and sort the elements in the interval [left, right] to make the entire array a sorted one.


  • 0
    B

    @Xnming Got you, thank you! :)


  • 0
    Q

    @Xnming Agree


  • 0

    @i_square I appreciate you idea, and I think it is the best.


Log in to reply
 

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