Sliding Window Maximum - Practice Coding Problems

Sliding Window Maximum - Problem

You are given an array of integers nums and a sliding window of size k which moves from the leftmost position to the rightmost position. At each position, you can only see the k numbers in the window.

Each time the sliding window moves right by one position, find the maximum element in the current window.

Return an array containing the maximum value of each window position.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,-1,-3,5,3,6,7], k = 3

› Output: [3,3,5,5,6,7]

💡 Note: Window [1,3,-1] → max=3, [3,-1,-3] → max=3, [-1,-3,5] → max=5, [-3,5,3] → max=5, [5,3,6] → max=6, [3,6,7] → max=7

Example 2 — Single Element Window

$ Input: nums = [1], k = 1

› Output: [1]

💡 Note: Only one element, so maximum is itself

Example 3 — All Same Elements

$ Input: nums = [7,7,7,7], k = 2

› Output: [7,7,7]

💡 Note: All elements are same, so every window has maximum 7

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,-1,-3,5,3,6,7] with window size k=3

Process

Slide window left to right, find maximum in each position

Output

Array of maximums [3,3,5,5,6,7]

Key Takeaway

🎯 Key Insight: Use a deque to maintain potential maximums in decreasing order, avoiding redundant comparisons

Asked in

a Amazon 50 G Google 45 M Microsoft 40 f Facebook 35

The key insight is to avoid recalculating maximums from scratch. The optimal deque approach maintains indices in decreasing order of values, ensuring O(n) time complexity by processing each element at most twice. Time: O(n), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Deque (Monotonic Queue)	O(n)	O(k)	Use deque to maintain decreasing order of potentially maximum elements
Max Heap with Lazy Deletion	O(n log k)	O(k)	Use max heap to track maximums, remove out-of-window elements lazily
Brute Force	O(n×k)	O(1)	For each window position, scan all k elements to find maximum

Deque (Monotonic Queue) — Algorithm Steps

Step 1: Initialize deque and process first k elements
Step 2: For each remaining element, remove out-of-window indices
Step 3: Remove smaller elements from back (they can't be maximum)
Step 4: Add current element, record front as window maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Process first k=3 elements, maintain decreasing order

Slide Window

Remove out-of-window indices, add new element

Optimal

Front of deque always has current maximum

Code -

solution.c — C

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

int* solution(int* nums, int numsSize, int k, int* returnSize) {
    if (numsSize == 0 || k == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    *returnSize = numsSize - k + 1;
    int* result = (int*)malloc(*returnSize * sizeof(int));
    int* dq = (int*)malloc(numsSize * sizeof(int));
    int front = 0, back = 0;
    
    // Process first k elements
    for (int i = 0; i < k; i++) {
        // Remove smaller elements from back
        while (back > front && nums[dq[back-1]] <= nums[i]) {
            back--;
        }
        dq[back++] = i;
    }
    
    // First window maximum
    result[0] = nums[dq[front]];
    int resultIdx = 1;
    
    // Process remaining elements
    for (int i = k; i < numsSize; i++) {
        // Remove out-of-window elements
        while (back > front && dq[front] <= i - k) {
            front++;
        }
        
        // Remove smaller elements from back
        while (back > front && nums[dq[back-1]] <= nums[i]) {
            back--;
        }
        
        dq[back++] = i;
        result[resultIdx++] = nums[dq[front]];
    }
    
    free(dq);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            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)

Each element is added and removed from deque at most once

✓ Linear Growth

Space Complexity

O(k)

Deque stores at most k indices in the worst case

✓ Linear Space

850.0K Views

High Frequency

~25 min Avg. Time

8.5K 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

Deque (Monotonic Queue) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler