LeetCode Problem 3555

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Stack, Greedy, Sorting, Monotonic Stack

Solution

Problem Understanding

We are given an array nums and a window size k. For every contiguous subarray of length k, we must determine the minimum length of a continuous segment that needs to be sorted so that the entire window becomes non-decreasing.

In other words, for each sliding window:

nums[i : i + k]

we want to find the shortest contiguous portion inside that window such that sorting only that portion makes the whole window sorted in non-decreasing order.

This is exactly the same as finding the length of the shortest unsorted continuous subarray inside each window.

If the window is already non-decreasing, then no sorting is required and the answer for that window is 0.

The output is an array of length:

n - k + 1

where the i-th element represents the answer for the window starting at index i.

The constraints are:

1 <= nums.length <= 1000
1 <= k <= nums.length

The array is relatively small. Since n is at most 1000, an algorithm that processes each window in O(k) time is completely practical because the total work is at most about one million operations.

Several edge cases are important:

• A window that is already sorted should return 0.
• A window that is strictly decreasing requires sorting the entire window.
• Duplicate values must be handled correctly because the target order is non-decreasing, not strictly increasing.
• When k = 1, every window contains a single element and is already sorted.
• When k = n, there is only one window, namely the entire array.

Approaches

Brute Force

For each window, we could try every possible subarray and check whether sorting that subarray makes the whole window non-decreasing.

Suppose a window has length k.

There are O(k²) possible segments. For each segment, we could sort it and verify whether the resulting window is sorted. Checking a candidate segment requires at least O(k) work, and sorting may cost O(k log k).

This approach is obviously correct because it directly tests every possible segment and chooses the shortest valid one. However, it is far too slow because each window would require roughly O(k³) work.

Key Insight

The problem inside a single window is exactly the classic "Shortest Unsorted Continuous Subarray" problem.

For a given window:

• Scan from left to right.
• Keep track of the largest value seen so far.
• Whenever the current value is smaller than that maximum, it is out of order and must belong to the unsorted region. Update the right boundary.

Similarly:

• Scan from right to left.
• Keep track of the smallest value seen so far.
• Whenever the current value is larger than that minimum, it is out of order and must belong to the unsorted region. Update the left boundary.

After both scans:

• If no violation was found, the window is already sorted.
• Otherwise, the answer is:

right_boundary - left_boundary + 1

Since each window can be processed in O(k) time, the total complexity becomes O((n - k + 1) * k).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((n - k + 1) * k³)	O(k)	Try every segment and verify
Optimal	O((n - k + 1) * k)	O(1)	Apply shortest-unsorted-subarray logic to each window

Algorithm Walkthrough

1. Create an answer array.
2. For every window starting at index start, consider the subarray:

nums[start : start + k]

3. Find the right boundary of the unsorted region.

Scan from left to right while maintaining the maximum value seen so far.

If the current value is smaller than that maximum, then this position violates the non-decreasing order and must belong to the segment that needs sorting. Update the right boundary to this index. 4. If no violation was found during the left-to-right scan, the window is already sorted.

Append 0 to the answer array and continue to the next window. 5. Find the left boundary of the unsorted region.

Scan from right to left while maintaining the minimum value seen so far.

If the current value is larger than that minimum, then this position also belongs to the unsorted region. Update the left boundary. 6. The shortest segment that must be sorted is exactly the interval between the two boundaries.

Compute:

length = right_boundary - left_boundary + 1

7. Append this length to the answer array.
8. Repeat for all windows.

Why it works

The left-to-right scan identifies every element that is smaller than a value that appeared earlier. Such elements cannot remain in their current position in a sorted array, so they determine the furthest right extent of the unsorted region.

The right-to-left scan identifies every element that is larger than a value appearing later. Such elements also cannot remain in their current position, so they determine the furthest left extent of the unsorted region.

Everything outside these two boundaries is already in its correct relative position. Therefore, sorting exactly the interval between the boundaries is sufficient and necessary, making it the minimum-length segment.

Python Solution

from typing import List

class Solution:
    def minSubarraySort(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        result = []

        for start in range(n - k + 1):
            window = nums[start:start + k]

            right = -1
            max_seen = window[0]

            for i in range(1, k):
                max_seen = max(max_seen, window[i])
                if window[i] < max_seen:
                    right = i

            if right == -1:
                result.append(0)
                continue

            left = -1
            min_seen = window[-1]

            for i in range(k - 2, -1, -1):
                min_seen = min(min_seen, window[i])
                if window[i] > min_seen:
                    left = i

            result.append(right - left + 1)

        return result

The implementation iterates through every sliding window independently.

For each window, the first scan maintains max_seen. Whenever a value is smaller than something that appeared earlier, the right boundary is updated. If no such violation exists, the window is already sorted and the answer is 0.

Otherwise, a second scan runs from right to left while maintaining min_seen. Whenever a value is larger than something that appears later, the left boundary is updated.

The interval between these two boundaries is exactly the shortest subarray that must be sorted. Its length is appended to the result.

Go Solution

func minSubarraySort(nums []int, k int) []int {
	n := len(nums)
	result := make([]int, 0, n-k+1)

	for start := 0; start <= n-k; start++ {
		window := nums[start : start+k]

		right := -1
		maxSeen := window[0]

		for i := 1; i < k; i++ {
			if window[i] > maxSeen {
				maxSeen = window[i]
			}
			if window[i] < maxSeen {
				right = i
			}
		}

		if right == -1 {
			result = append(result, 0)
			continue
		}

		left := -1
		minSeen := window[k-1]

		for i := k - 2; i >= 0; i-- {
			if window[i] < minSeen {
				minSeen = window[i]
			}
			if window[i] > minSeen {
				left = i
			}
		}

		result = append(result, right-left+1)
	}

	return result
}

The Go implementation follows exactly the same logic as the Python version.

The window is represented as a slice of the original array, which avoids copying data. Integer overflow is not a concern because all values are at most 10^6, and the algorithm only performs comparisons. Empty slices never occur because k >= 1 is guaranteed by the constraints.

Worked Examples

Example 1

Input

nums = [1,3,2,4,5]
k = 3

Window [1,3,2]

Left-to-right scan

i	value	max_seen	right
0	1	1	-1
1	3	3	-1
2	2	3	2

Right-to-left scan

i	value	min_seen	left
2	2	2	-1
1	3	2	1
0	1	1	1

Result:

2 - 1 + 1 = 2

Window [3,2,4]

Left-to-right scan

i	value	max_seen	right
0	3	3	-1
1	2	3	1
2	4	4	1

Right-to-left scan

i	value	min_seen	left
2	4	4	-1
1	2	2	-1
0	3	2	0

Result:

1 - 0 + 1 = 2

Window [2,4,5]

Left-to-right scan

i	value	max_seen	right
0	2	2	-1
1	4	4	-1
2	5	5	-1

No violation occurs.

Result:

0

Final output:

[2,2,0]

Example 2

Input

nums = [5,4,3,2,1]
k = 4

Window [5,4,3,2]

Left-to-right scan

i	value	max_seen	right
0	5	5	-1
1	4	5	1
2	3	5	2
3	2	5	3

Right-to-left scan

i	value	min_seen	left
3	2	2	-1
2	3	2	2
1	4	2	1
0	5	2	0

Result:

3 - 0 + 1 = 4

Window [4,3,2,1]

The same reasoning applies.

Result:

4

Final output:

[4,4]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n - k + 1) * k)	Each window is scanned twice
Space	O(1)	Only a few variables are maintained

Each window requires one left-to-right scan and one right-to-left scan, both taking O(k) time. Since there are n - k + 1 windows, the total running time is O((n - k + 1) * k). The algorithm uses only constant extra space beyond the output array.

Test Cases

sol = Solution()

assert sol.minSubarraySort([1, 3, 2, 4, 5], 3) == [2, 2, 0]  # example 1

assert sol.minSubarraySort([5, 4, 3, 2, 1], 4) == [4, 4]  # example 2

assert sol.minSubarraySort([1], 1) == [0]  # single element

assert sol.minSubarraySort([1, 2, 3, 4], 4) == [0]  # already sorted

assert sol.minSubarraySort([4, 3, 2, 1], 4) == [4]  # fully reversed

assert sol.minSubarraySort([2, 2, 2, 2], 3) == [0, 0]  # duplicates

assert sol.minSubarraySort([1, 5, 3, 4, 2], 5) == [4]  # unsorted middle section

assert sol.minSubarraySort([1, 2, 5, 3, 4], 5) == [3]  # suffix disorder

assert sol.minSubarraySort([3, 1, 2], 3) == [3]  # entire window needed

assert sol.minSubarraySort([1, 2, 1, 2, 1], 2) == [0, 2, 0, 2]  # many small windows

Test Summary

Test	Why
[1,3,2,4,5], k=3	Official example
[5,4,3,2,1], k=4	Official example, fully decreasing windows
[1], k=1	Minimum input size
[1,2,3,4], k=4	Already sorted array
[4,3,2,1], k=4	Entire array must be sorted
[2,2,2,2], k=3	Duplicate values
[1,5,3,4,2], k=5	Large unsorted region
[1,2,5,3,4], k=5	Disorder near the end
[3,1,2], k=3	Whole window required
[1,2,1,2,1], k=2	Multiple overlapping windows

Edge Cases

Window Already Sorted

A common bug is returning a positive length even when the window is already non-decreasing. In a sorted window, the left-to-right scan never finds a value smaller than a previous maximum, so right remains -1. The implementation explicitly checks this condition and returns 0.

All Elements Equal

Since the desired order is non-decreasing, equal values are perfectly valid. An implementation that mistakenly uses strict comparisons in the wrong direction may incorrectly mark duplicates as violations. The algorithm only treats value < max_seen and value > min_seen as violations, so equal values are handled correctly.

Completely Decreasing Window

For a window such as [5,4,3,2], every position except the first violates the left-to-right condition, and every position except the last violates the right-to-left condition. The computed boundaries become the first and last indices of the window, producing the full window length. This correctly reflects the fact that the entire window must be sorted.

Single Element Windows

When k = 1, every window contains exactly one element. Such a window is always sorted. The scans immediately conclude that there are no violations, and the answer is 0 for every window.

Disorder Near Only One End

Cases such as [1,2,5,3,4] can be tricky because only a suffix appears incorrect. The boundary scans naturally expand the unsorted region only as far as necessary, ensuring that the algorithm returns the minimum segment length rather than sorting more of the window than required.