Problem Description

You are given an integer array nums and an integer k.

The problem asks you to process sliding windows of size k across the array. For each window (contiguous subarray of length k), you need to find the minimum length of a continuous segment within that window that needs to be sorted to make the entire window non-decreasing.

Here's what you need to determine for each window:

• If the window is already sorted in non-decreasing order, the answer is 0
• Otherwise, find the shortest continuous portion that, when sorted, would make the entire window non-decreasing

The output should be an array of length n - k + 1, where each element represents the answer for the corresponding window starting at that position.

For example, if you have a window [3, 1, 2, 4]:

• The window is not sorted (not non-decreasing)
• The segment [3, 1, 2] needs to be sorted to get [1, 2, 3, 4]
• So the minimum length would be 3

The key insight is that for each window, you need to identify the leftmost and rightmost positions where elements are out of order, and the segment between them (inclusive) is what needs to be sorted.

Intuition

To understand which segment needs sorting, let's think about what makes an element "out of place" in a sorted array.

When we traverse an array from left to right, we keep track of the maximum value seen so far. If we encounter an element smaller than this maximum, it means this element is out of position - it should have appeared earlier in a sorted sequence. This gives us the rightmost boundary of our segment that needs sorting.

Similarly, when traversing from right to left, we track the minimum value seen so far. If we encounter an element larger than this minimum, it's also out of position - it should have appeared later in a sorted sequence. This gives us the leftmost boundary of our segment.

The key insight is that any element between these two boundaries (inclusive) needs to be part of the sorted segment. Why? Because:

1. The leftmost out-of-place element found from the right-to-left scan needs to move right
2. The rightmost out-of-place element found from the left-to-right scan needs to move left
3. All elements between them must be rearranged to accommodate these movements

For each window of size k, we apply this two-pointer technique:

• Start with l = -1 and r = -1 (indicating no segment needs sorting)
• Scan left to right: if nums[j] < max_so_far, update r = j
• Scan right to left: if nums[j] > min_so_far, update l = j
• If neither l nor r was updated, the window is already sorted (return 0)
• Otherwise, return r - l + 1 as the length of the segment to sort

This approach efficiently identifies the minimal segment because it finds the exact boundaries where the non-decreasing property is violated from both directions.

Learn more about Stack, Greedy, Two Pointers, Sorting and Monotonic Stack patterns.

Solution Approach

The solution implements the intuition we discussed by creating a helper function f(i, j) that processes each window from index i to j (inclusive).

Here's how the implementation works:

Helper Function f(i, j):

1. Initialize tracking variables:

   • mi = inf and mx = -inf to track minimum and maximum values
   • l = -1 and r = -1 to mark the left and right boundaries of the segment to sort

2. Single loop with bidirectional processing: The function uses a clever technique to scan from both directions in a single loop:

   • For position k from i to j:
     • Left-to-right scan: Check position k
       • If mx > nums[k], this element is smaller than the max seen so far, so update r = k
       • Otherwise, update mx = nums[k] as the new maximum
     • Right-to-left scan: Check position p = j - k + i (mirror position from the right)
       • If mi < nums[p], this element is larger than the min seen so far, so update l = p
       • Otherwise, update mi = nums[p] as the new minimum

3. Return the result:

   • If r == -1, no updates were made, meaning the window is already sorted, return 0
   • Otherwise, return r - l + 1 as the length of the segment that needs sorting

Main Function:

The main function simply applies the helper function to each possible window:

return [f(i, i + k - 1) for i in range(n - k + 1)]

This generates a list where each element represents the minimum sorting length for the window starting at index i with length k.

Time Complexity: O((n - k + 1) * k) = O(n * k) since we process each of the n - k + 1 windows, and for each window, we scan k elements.

Space Complexity: O(1) extra space (not counting the output array), as we only use a constant number of variables in the helper function.

Example Walkthrough

Let's walk through the solution with nums = [1, 4, 3, 2, 5] and k = 3.

We need to process 3 windows of size 3: [1,4,3], [4,3,2], and [3,2,5].

Window 1: [1, 4, 3] (indices 0 to 2)

Initialize: mi = inf, mx = -inf, l = -1, r = -1

Loop iteration (k goes from 0 to 2):

• k=0:

  • Left scan at index 0: nums[0]=1. Since mx=-inf < 1, update mx=1
  • Right scan at index 2 (p=2-0+0=2): nums[2]=3. Since mi=inf > 3, update mi=3

• k=1:

  • Left scan at index 1: nums[1]=4. Since mx=1 < 4, update mx=4
  • Right scan at index 1 (p=2-1+0=1): nums[1]=4. Since mi=3 < 4, found out-of-place element, set l=1

• k=2:

  • Left scan at index 2: nums[2]=3. Since mx=4 > 3, found out-of-place element, set r=2
  • Right scan at index 0 (p=2-2+0=0): nums[0]=1. Since mi=3 > 1, update mi=1

Result: r=2, l=1, so length = 2-1+1 = 2 (need to sort [4,3] to get [1,3,4])

Window 2: [4, 3, 2] (indices 1 to 3)

Initialize: mi = inf, mx = -inf, l = -1, r = -1

Loop iteration:

• k=0:

  • Left scan at index 1: nums[1]=4. Since mx=-inf < 4, update mx=4
  • Right scan at index 3 (p=3-0+1=3): nums[3]=2. Since mi=inf > 2, update mi=2

• k=1:

  • Left scan at index 2: nums[2]=3. Since mx=4 > 3, found out-of-place element, set r=2
  • Right scan at index 2 (p=3-1+1=2): nums[2]=3. Since mi=2 < 3, found out-of-place element, set l=2

• k=2:

  • Left scan at index 3: nums[3]=2. Since mx=4 > 2, found out-of-place element, set r=3
  • Right scan at index 1 (p=3-2+1=1): nums[1]=4. Since mi=2 < 4, found out-of-place element, set l=1

Result: r=3, l=1, so length = 3-1+1 = 3 (need to sort entire window [4,3,2] to get [2,3,4])

Window 3: [3, 2, 5] (indices 2 to 4)

Initialize: mi = inf, mx = -inf, l = -1, r = -1

Loop iteration:

• k=0:

  • Left scan at index 2: nums[2]=3. Since mx=-inf < 3, update mx=3
  • Right scan at index 4 (p=4-0+2=4): nums[4]=5. Since mi=inf > 5, update mi=5

• k=1:

  • Left scan at index 3: nums[3]=2. Since mx=3 > 2, found out-of-place element, set r=3
  • Right scan at index 3 (p=4-1+2=3): nums[3]=2. Since mi=5 > 2, update mi=2

• k=2:

  • Left scan at index 4: nums[4]=5. Since mx=3 < 5, update mx=5
  • Right scan at index 2 (p=4-2+2=2): nums[2]=3. Since mi=2 < 3, found out-of-place element, set l=2

Result: r=3, l=2, so length = 3-2+1 = 2 (need to sort [3,2] to get [2,3,5])

Final Output: [2, 3, 2]

Solution Implementation

Time and Space Complexity

The time complexity is O(n × k), where n is the length of the array nums and k is the window size. This is because:

• The outer list comprehension iterates n - k + 1 times (for each possible window starting position)
• For each iteration, the function f(i, j) is called, which contains a loop that runs exactly k times (from i to j + 1 where j = i + k - 1)
• Therefore, the total operations are (n - k + 1) × k, which simplifies to O(n × k)

The space complexity is O(1) for the algorithm itself (excluding the output array). The function f only uses a constant amount of extra space with variables mi, mx, l, r, and loop variables, regardless of the input size. The output list has size n - k + 1, but this is not counted as part of the space complexity of the algorithm itself.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Detection Logic

The Pitfall: A common mistake is incorrectly identifying which elements are "out of order." Developers often confuse the conditions for updating the left and right boundaries. Specifically:

• When scanning left-to-right, finding nums[idx] < max_from_left means this element needs to be included in the sorting range (update right boundary)
• When scanning right-to-left, finding nums[idx] > min_from_right means this element needs to be included in the sorting range (update left boundary)

Why it happens: The confusion arises because the logic seems counterintuitive - when going left-to-right, we update the RIGHT boundary, and when going right-to-left, we update the LEFT boundary.

Example of incorrect implementation:

# WRONG: Swapped boundary updates
if max_from_left > nums[idx]:
    left_boundary = idx  # Wrong! Should update right_boundary

Solution: Remember that:

• Left-to-right scan finds the rightmost position that violates sorted order
• Right-to-left scan finds the leftmost position that violates sorted order

2. Off-by-One Errors in Mirror Index Calculation

The Pitfall: When calculating the mirror position for bidirectional scanning, it's easy to make off-by-one errors:

# Common mistakes:
right_idx = end - idx  # Missing the start offset
right_idx = start + end - idx - 1  # Unnecessary -1
right_idx = j - (idx - i)  # Overly complex

Solution: The correct formula is: right_idx = end - idx + start

• When idx = start, right_idx = end (first from left maps to last from right)
• When idx = end, right_idx = start (last from left maps to first from right)

3. Mishandling Already Sorted Windows

The Pitfall: Forgetting to handle the case where the window is already sorted, or incorrectly determining this condition:

# WRONG: Checking wrong variable
if left_boundary == -1:  # Only checks left, not both
    return 0

# WRONG: Not initializing boundaries properly
left_boundary = 0  # Should be -1 to detect no changes

Solution: Initialize both boundaries to -1 and check if either remains -1 (since both should be updated if any element is out of order):

if right_boundary == -1:  # or left_boundary == -1
    return 0

4. Confusion Between Strict and Non-Strict Ordering

The Pitfall: Using strict inequality when non-decreasing order (allowing duplicates) is required:

# WRONG: Strict inequality doesn't handle duplicates correctly
if max_from_left >= nums[idx]:  # Should be >
    right_boundary = idx

Solution: Use strict inequalities (> and <) to allow duplicate values in non-decreasing order:

• max_from_left > nums[idx] - only update if strictly greater
• min_from_right < nums[right_idx] - only update if strictly less

5. Inefficient Window Processing

The Pitfall: Creating a new array or using sorting for each window unnecessarily:

# INEFFICIENT: Actually sorting to check
def find_unsorted_length(start, end):
    window = nums[start:end+1]
    sorted_window = sorted(window)
    # Then comparing to find differences...

Solution: Use the two-pointer approach without modifying or copying the array. The algorithm only needs to track boundaries, not perform actual sorting.