Crack the Backend

Problem Statement

Given an array nums and an integer k, return an array where the i-th element is the maximum value in the sliding window [i, i+k-1] (window of size k moving from left to right).

The window moves one position at a time; we need the max of each window. Naive O(n*k) is to scan each window; we want O(n).
If nums.length < k, we have at most one window (or none); handle edge cases as required (e.g. return empty or the max of the whole array).

Key Observations

A monotonic deque (strictly decreasing by value, storing indices) gives the current window maximum at the front: the front index is always the max of the current window because any element to the left of it that is smaller cannot be the max once the front is in the window (and we remove indices that leave the window).
When we add nums[right], we pop from the back of the deque all indices whose value is <= nums[right] (they can never be the max of any future window containing right). Then push right. The front is the index of the current max; if the front index has left the window, pop it from the front.
Each index is pushed once and popped at most once, so total time is O(n).

Approach

High-level: Maintain a deque of indices such that the corresponding values are in decreasing order. The front is the index of the current window maximum. When the window slides, remove indices that leave the window and indices that become useless (smaller than the new element).

Steps:

Deque stores indices. For right from 0 to n-1: (a) Remove from front if front index < right - k + 1 (out of window). (b) Remove from back while nums[back] <= nums[right]; then push right. (c) If right >= k - 1, the front index is the max for the window ending at right; append nums[front] to the result.
Return the result array.

Implementation

Java

public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();
    int[] result = new int[nums.length - k + 1];

    for (int i = 0; i < nums.length; i++) {
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
            dq.pollFirst();
        }

        while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
            dq.pollLast();
        }

        dq.offerLast(i);

        if (i >= k - 1) {
            result[i - k + 1] = nums[dq.peekFirst()];
        }
    }

    return result;
}

Test Cases

Example 1

Input

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

Expected

[3,3,5,5,6,7]

Explanation

Max of each window of size 3.

Complexity Analysis

Time: O(n); each index pushed and popped at most once.
Space: O(k) for the deque.

Follow-ups

Support minimum sliding window or range sum in the window.