[C++] Clean Code 2 Solution - Sort O(NlgN) & max min vectors O(N)


  • 5

    Sort

    class Solution {
    public:
        int findUnsortedSubarray(vector<int>& nums) {
            vector<int> sorted(nums);
            sort(sorted.begin(), sorted.end());
            int n = nums.size(), i = 0, j = n - 1;
            while (i < n && nums[i] == sorted[i]) {
                i++;
            }
            while (j > i && nums[j] == sorted[j]) {
                j--;
            }
            return j + 1 - i;
        }
    };
    

    max on left, min on right - O(N)
    The idea is that:

    1. From the left, for a number to stay untouched, there need to be no number less than it on the right hand side;
    2. From the right, for a number to stay untouched, there need to be no number greater than it on the left hand side;

    Those 2 can be easily checked if we build 2 vectors:

    1. max so far from the left,
    2. and min so far from the right;
    /**
     *            /------------\
     * nums:  [2, 6, 4, 8, 10, 9, 15]
     * minr:   2  4  4  8   9  9  15
     *         <--------------------
     * maxl:   2  6  6  8  10 10  15
     *         -------------------->
     */
    class Solution {
    public:
        int findUnsortedSubarray(vector<int>& nums) {
            int n = nums.size();
            vector<int> maxlhs(n);   // max number from left to cur
            vector<int> minrhs(n);   // min number from right to cur
            for (int i = n - 1, minr = INT_MAX; i >= 0; i--) minrhs[i] = minr = min(minr, nums[i]);
            for (int i = 0,     maxl = INT_MIN; i < n;  i++) maxlhs[i] = maxl = max(maxl, nums[i]);
    
            int i = 0, j = n - 1;
            while (i < n && nums[i] <= minrhs[i]) i++;
            while (j > i && nums[j] >= maxlhs[j]) j--;
    
            return j + 1 - i;
        }
    };
    

  • 0
    A

    Given input - 2 6 4 8 10 9 15
    Please explain. I'm dry running in this code and getting output 3.
    Thanks


  • 0

    @aryan_gupta I get 5, can you retry?


  • 0
    A

    @alexander i tried. Thank alot. I understood.


  • 0
    This post is deleted!

  • 0

    @alexander The first solution is easy to think of. And the second solution is awesome to solve problem in O(n) space and O(n) time. Thank you for your post!


  • 0
    U

    nice solution!


Log in to reply
 

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