C++ O(N) Time O(1) Space 43ms Two Pass Using Min/Max Comparison


  • 0
    M
    class Solution {
    public:
        int findUnsortedSubarray(vector<int>& nums) {
            int nmax = INT_MIN, nmin = INT_MAX, l = -1, r = -2;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] < nmax) r = i;
                nmax = max(nmax, nums[i]);
            }
            for (int i = nums.size() - 1; i >= 0; --i) {
                if (nums[i] > nmin) l = i;
                nmin = min(nmin, nums[i]);
            }
            return r - l + 1;
        }
    };
    

  • 0
    H
    int findUnsortedSubarray(vector<int>& nums)
    {
    	int nStartIdx = -1;
    	int nEndIdx = -2;
    	int nArrSize = nums.size() - 1;
    	int nMin = 0x7FFFFFFF;
    	int nMax = 0x80000000;
    
    	for (int i = 0; i < nums.size(); ++i)
    	{
    		//! check max is lower than current value
    		if (nums[i] < nMax)
    			nEndIdx = i;
    		nMax = max(nMax, nums[i]);
    
    		//! check min is higher than current value
    		if (nums[nArrSize - i] > nMin)
    			nStartIdx = nArrSize - i;
    		nMin = min(nMin, nums[nArrSize - i]);
    
    	}
    	return (nEndIdx - nStartIdx + 1);
    }
    

    I tried to merge in single loop by your logic.
    Thank you for nice idea! :D


Log in to reply
 

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