Shortest Unsorted Continuous Subarray Solution in Java

Navigate to Other Solutions
C++ Solution
Python Solution


class Solution {
  public int findUnsortedSubarray(int[] nums) {
    final int n = nums.length;
    int mn = Integer.MAX_VALUE;
    int mx = Integer.MIN_VALUE;
    boolean meetDecrease = false;
    boolean meetIncrease = false;

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

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

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

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

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

Problem Description

Ah, the classic dilemma of the Shortest Unsorted Continuous Subarray! Imagine you’re at a party, and everyone is dancing in perfect rhythm. Suddenly, you spot that one friend who thinks they can breakdance but ends up looking like a flailing octopus. You just want to pull them aside and fix their moves so the whole party doesn’t turn into a chaotic mess.

In the world of arrays, this problem is akin to finding the smallest subarray that, if sorted, would make the entire array sorted. You’re given an array of integers, and your task is to identify the shortest continuous subarray that, when sorted, will result in the entire array being sorted.

The Challenge

Given an integer array nums, your goal is to return the length of the shortest subarray that needs to be sorted in order for the entire array to be sorted. If the array is already sorted, return 0.

Approach Explanation

The approach taken in this solution is quite clever. It involves two main passes through the array:

Finding the Minimum and Maximum: The first loop identifies the minimum value (mn) that needs to be included in the sorting process by checking where the array starts to decrease. The second loop does the opposite, finding the maximum value (mx) where the array starts to increase.
Identifying the Bounds: After determining mn and mx, the next step is to find the left (l) and right (r) bounds of the subarray that needs sorting. If l is greater than r, it means the array is already sorted, and we return 0. Otherwise, the length of the unsorted subarray is calculated as r - l + 1.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array. We traverse the array a constant number of times.

Space Complexity: O(1), as we are using a fixed amount of extra 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 in alphabetical order, but a few have been misplaced. You need to identify the smallest section of books that, if rearranged, would make the entire shelf look neat and tidy again. This is exactly what the Shortest Unsorted Continuous Subarray problem is about!