Python O(n) using window

  • 0

    Generate a window whenever we see an unsorted pair (consecutive). This can be done by extending the right end of the window until it's greater than the prior (greater) of the pair and extending the left end of the window until the left end is less than the latter (lesser) of the pair. This effectively searches for their correct spots. Key is that whenever we find another unsorted pair, we only update the right end (as we've found a wider window) then only check this pair starting from the two ends of the window. This is due to the fact that the minimum window at the point we find a second unsorted pair, we know that we have to sort from the left end until the newly found pair. Since the window can only cover up to O(n) or the entire array, this algorithm will be doing O(n) checks at most since it doesn't search within the window.

    def findUnsortedSubarray(self, nums):
            start, end = float("inf"), float("-inf")
            for i in range(1, len(nums)):
                if nums[i] < nums[i-1]:
                    start, end = min(start, i-1), max(end, i)
                    while start >= 0 and nums[start] > nums[i]:
                        start -= 1
                    while end < len(nums) and nums[end] < nums[i-1]:
                        end += 1
            return max(end - start - 1, 0)

Log in to reply

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