Shortest Unsorted Continuous Subarray Solution in C++

Problem Description

The “Shortest Unsorted Continuous Subarray” problem is about identifying the shortest subarray that, if sorted, would make the entire array sorted. Imagine you’re at a party, and everyone is dancing in perfect rhythm. But then, there’s that one guy who thinks he’s the star of the show, doing the worm while everyone else is doing the cha-cha. Your job is to figure out how to get that guy back in line (or at least find out how many people you need to move around to restore order).

Code Solution

Copy Code

class Solution {
 public:
  int findUnsortedSubarray(vector& nums) {
    const int n = nums.size();
    int mn = INT_MAX;
    int mx = INT_MIN;
    bool meetDecrease = false;
    bool meetIncrease = false;

    for (int i = 1; i < n; ++i) {
      if (nums[i] < nums[i - 1])
        meetDecrease = true;
      if (meetDecrease)
        mn = min(mn, nums[i]);
    }

    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] > nums[i + 1])
        meetIncrease = true;
      if (meetIncrease)
        mx = max(mx, nums[i]);
    }

    int l;
    for (l = 0; l < n; ++l)
      if (nums[l] > mn)
        break;

    int r;
    for (r = n - 1; r >= 0; --r)
      if (nums[r] < mx)
        break;

    return l < r ? r - l + 1 : 0;
  }
};

Approach

The approach taken in this solution is to traverse the array to find the minimum value that needs to be included in the unsorted subarray by checking for decreases in the array. Then, we do a reverse traversal to find the maximum value that needs to be included. Finally, we determine the left and right boundaries of the unsorted subarray and return its length.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of elements in the array. We traverse the array a couple of times, but it’s still linear.
• Space Complexity: O(1), as we are using a constant amount of space regardless of the input size.

Real-World Example

Let’s say you’re organizing a bookshelf. You have a collection of books that are mostly sorted by height, but there’s that one towering novel that’s been shoved in the middle of a row of paperbacks. To restore order, you need to identify the shortest section of books that, if rearranged, would make the entire shelf look neat and tidy. This is essentially what the problem is asking you to do with the array!