Smallest Subarray to Sort in Every Sliding Window

Smallest Subarray to Sort in Every Sliding Window - Problem

Array Two Pointers Stack Greedy Sorting Monotonic Stack Medium

You are given an integer array nums and an integer k. For each contiguous subarray of length k, determine the minimum length of a continuous segment that must be sorted so that the entire window becomes non-decreasing (sorted in ascending order).

Important: If the window is already sorted, its required length is zero.

Return an array of length n - k + 1 where each element corresponds to the answer for its respective window position.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,1,3,2,5], k = 3

› Output: [3,2,2]

💡 Note: Window [4,1,3] needs entire array sorted (length 3). Window [1,3,2] needs positions 1,2 sorted (length 2). Window [3,2,5] needs positions 0,1 sorted (length 2).

Example 2 — Already Sorted Window

$ Input: nums = [1,2,3,4,5], k = 3

› Output: [0,0,0]

💡 Note: All windows [1,2,3], [2,3,4], [3,4,5] are already sorted, so required length is 0 for each.

Example 3 — Single Element Window

$ Input: nums = [5,4,3,2,1], k = 1

› Output: [0,0,0,0,0]

💡 Note: All windows have size 1, which are trivially sorted, so required length is 0 for each.

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [4,1,3,2,5] with sliding windows of size k=3

Process

For each window, find minimum range that needs sorting

Output

Array of minimum sort lengths [3,2,2]

Key Takeaway

🎯 Key Insight: Compare each window with its sorted version to find minimum disorder range

Asked in

G Google 45 a Amazon 35 M Microsoft 30 A Apple 25

The key insight is to compare each sliding window with its sorted version to find the minimum range that differs. The optimal approach uses two-pass boundary detection to find positions where elements are out of place. Time: O(n × k), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subarrays	O(n × k³ × k log k)	O(k)	For each window, try all possible sorting ranges and find minimum
Two-Pass Boundary Detection	O(n × k)	O(1)	Find leftmost and rightmost positions that break the sorted order

Brute Force - Try All Subarrays — Algorithm Steps

Iterate through all windows of size k
For each window, try all possible continuous subarrays
Sort each subarray and check if window becomes sorted
Return minimum length that works

Visualization

Tap to expand

Step-by-Step Walkthrough

Window Selection

Take sliding window of size k

Try All Ranges

Test sorting every possible continuous subarray

Find Minimum

Return shortest range that makes window sorted

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums, int numsSize, int k, int* returnSize) {
    *returnSize = numsSize - k + 1;
    int* result = (int*)malloc(*returnSize * sizeof(int));
    
    for (int i = 0; i <= numsSize - k; i++) {
        int* window = (int*)malloc(k * sizeof(int));
        for (int j = 0; j < k; j++) {
            window[j] = nums[i + j];
        }
        
        int minLength = 0;
        
        // Check if already sorted
        int isSorted = 1;
        for (int j = 0; j < k - 1; j++) {
            if (window[j] > window[j + 1]) {
                isSorted = 0;
                break;
            }
        }
        
        if (isSorted) {
            result[i] = 0;
            free(window);
            continue;
        }
        
        // Try all possible subarrays to sort
        int found = 0;
        for (int length = 1; length <= k && !found; length++) {
            for (int start = 0; start <= k - length; start++) {
                int* testWindow = (int*)malloc(k * sizeof(int));
                for (int j = 0; j < k; j++) {
                    testWindow[j] = window[j];
                }
                
                qsort(testWindow + start, length, sizeof(int), compare);
                
                // Check if entire window is now sorted
                int nowSorted = 1;
                for (int j = 0; j < k - 1; j++) {
                    if (testWindow[j] > testWindow[j + 1]) {
                        nowSorted = 0;
                        break;
                    }
                }
                
                if (nowSorted) {
                    minLength = length;
                    found = 1;
                    free(testWindow);
                    break;
                }
                free(testWindow);
            }
        }
        
        result[i] = minLength;
        free(window);
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(nums, numsSize, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k³ × k log k)

n-k+1 windows, k² possible subarrays per window, k log k to sort each

⚡ Linearithmic

Space Complexity

O(k)

Extra space for copying and sorting subarrays

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler