Shortest Unsorted Continuous Subarray Solution in Python

Problem Description

Ah, the classic dilemma of the “Shortest Unsorted Continuous Subarray.” Imagine you’re at a party, and everyone is dancing in perfect sync, except for that one guy who’s doing the Macarena while everyone else is doing the cha-cha. You just want to grab him and pull him into the groove, but how do you know how far to pull him? This problem is essentially asking you to find the smallest subarray that, if sorted, would make the entire array look like it’s been to a dance class.

In simpler terms, given an array of integers, your task is to find the length of the shortest continuous subarray that needs to be sorted in order for the entire array to be sorted. If the array is already sorted, you can just sit back and enjoy the party!

Code Solution

import math

class Solution:
    def findUnsortedSubarray(self, nums: list[int]) -> int:
        mn = math.inf
        mx = -math.inf
        flag = False

        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:
                flag = True
            if flag:
                mn = min(mn, nums[i])

        flag = False

        for i in reversed(range(len(nums) - 1)):
            if nums[i] > nums[i + 1]:
                flag = True
            if flag:
                mx = max(mx, nums[i])

        for l in range(len(nums)):
            if nums[l] > mn:
                break

        for r, num in reversed(list(enumerate(nums))):
            if num < mx:
                break

        return 0 if l >= r else r - l + 1
    

Approach

The approach taken in this code is quite elegant. It first identifies the minimum and maximum values that are out of place in the array. It does this by traversing the array twice: once from the left to find the minimum value that needs to be included in the unsorted subarray, and once from the right to find the maximum. After identifying these values, it determines the left and right boundaries of the subarray that needs sorting. Finally, it calculates the length of this subarray.

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the input array. The algorithm makes a constant number of passes through the array.
• Space Complexity: O(1), as it uses a fixed amount of extra space regardless of the input size.

Real-World Example

Imagine you’re organizing a bookshelf. You have a collection of books that are mostly in alphabetical order, but a few have been misplaced. You need to find the shortest section of books that, if rearranged, would make the entire shelf look neat and tidy. This problem is akin to finding that section of misplaced books on your shelf!