Maximum Values in Subsequences — Problem Statement & Solution Guide

Sliding WindowHardSliding Window Maximum

TimeO(n)

SpaceO(k)

Problem Description

Given an array of integers representing a discrete signal and an integer k denoting the window size, compute the maximum value within every contiguous subarray of length k as the window slides from the start to the end of the array.

The input consists of an array nums of length n and an integer k, where 1 <= k <= n. The output should be an array of length n - k + 1, where the i-th element corresponds to the maximum value in the subarray nums[i ... i + k - 1].

For example, if nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the sliding windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], and [3,6,7]. The maximums are 3, 3, 5, 5, 6, and 7 respectively.

DSA Pattern Breakdown

"Maximum Values in Subsequences"

hard

WHY DOES IT MATTER?

Sliding‑window maximum is a canonical example of the monotonic queue pattern, which appears in real‑time analytics, stock‑price monitoring, and any scenario requiring fast, rolling aggregates. Mastering this pattern equips engineers to design low‑latency services that process streams without recomputing from scratch.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that any element smaller than a newer element can never become the maximum while the newer one remains in the window, allowing us to prune it immediately. This pruning ensures each element is processed O(1) times overall, collapsing the naïve O(n·k) bound to O(n).

REAL-WORLD CONNECTION

Think of a moving surveillance camera that continuously records the highest temperature in its field of view. Instead of re‑scanning every pixel each frame, the system keeps a list of candidate hot spots; as the view shifts, outdated spots are discarded and new hotter spots replace weaker ones, mirroring the deque’s behavior.

During an interview, implement the deque first, then add the two housekeeping steps: (1) pop indices that are out of the current window range, and (2) maintain decreasing order by popping smaller values from the back before pushing the new index.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The sliding‑window maximum problem asks for the greatest element in every contiguous subarray of size k. A naïve solution recomputes the maximum for each window by scanning k elements, leading to O(n·k) time, which becomes prohibitive when n and k approach 10^5 or larger. The optimal solution relies on a monotonic deque (double‑ended queue) that stores indices of candidates in decreasing order of their values. As the window slides, elements that fall out of the window are removed from the front, and any new element that is smaller than the deque’s tail is discarded because it can never become a maximum while a larger element remains in the window. This invariant guarantees that the deque’s front always holds the index of the current window’s maximum.

By maintaining this structure, each array element is inserted and removed at most once, yielding linear O(n) time. The space usage is O(k) in the worst case, but often much smaller because the deque holds only a subset of indices that are potential maxima. This paradigm exemplifies the broader class of problems solvable with monotonic data structures, where ordering constraints enable amortized constant‑time updates while preserving essential information for each window.

The approach also generalizes to other sliding‑window aggregates (minimum, sum, count of distinct elements) by swapping the monotonic condition or augmenting the deque with auxiliary data. Understanding why the naïve method fails and how the monotonic deque enforces a strict ordering is key to mastering hard‑level sliding‑window challenges in interviews.

Interview Questions on This Problem

Q1How would you modify the monotonic deque solution to return the minimum of each sliding window instead of the maximum?

Use an increasing deque instead of a decreasing one: while the deque’s tail holds values greater than the incoming element, pop them. The front then always contains the index of the minimum for the current window.

Q2Can you solve the sliding‑window maximum problem in O(n log k) time without a deque? If so, describe the method.

Yes, by using a balanced binary search tree (e.g., multiset) or a max‑heap with lazy deletion. Insert each new element and remove the element that slides out; the tree/heap’s top gives the current maximum, leading to O(log k) per operation and O(n log k) total.

Q3Explain how you would handle the case where k equals 1 or n in your implementation, and why these edge cases are trivial.

When k = 1, each window contains a single element, so the output is the original array; the algorithm can return a copy directly. When k = n, there is only one window covering the whole array, so the answer is the global maximum, which can be found with a single linear scan.

Examples

Example 1

Input

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

Output

[5, 7, 7, 8, 8]

Explanation: Window 1: [2,1,5] -> max 5. Window 2: [1,5,7] -> max 7. Window 3: [5,7,3] -> max 7. Window 4: [7,3,8] -> max 8. Window 5: [3,8,4] -> max 8.

Example 2

Input

nums = [10, -2, 4, 0, 7, 1, 9], k = 4

Output

[10, 4, 7, 9]

Explanation: Window 1: [10,-2,4,0] -> max 10. Window 2: [-2,4,0,7] -> max 7. Window 3: [4,0,7,1] -> max 7. Window 4: [0,7,1,9] -> max 9.

Example 3

Input

nums = [5, 5, 5, 5], k = 2

Output

[5, 5, 5]

Explanation: Window 1: [5,5] -> max 5. Window 2: [5,5] -> max 5. Window 3: [5,5] -> max 5.

Example 4

Input

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

Output

[-1, -1, -2]

Explanation: Window 1: [-3,-1,-4] -> max -1. Window 2: [-1,-4,-2] -> max -1. Window 3: [-4,-2,-5] -> max -2.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= k <= nums.length

Optimal Approach & Strategy

Maintain a decreasing deque of indices, updating it in O(1) amortized time per element so each element is processed only twice.

Brute Force Approach

For each window, scan all k elements to find the maximum, repeating this for every possible window.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const result = [];
    const dq = []; // Stores indices
    
    for (let i = 0; i < nums.length; i++) {
        // Remove indices out of the current window
        if (dq.length > 0 && dq[0] <= i - k) {
            dq.shift();
        }
        
        // Remove indices of elements smaller than the current element
        while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) {
            dq.pop();
        }
        
        dq.push(i);
        
        // The front of the deque is the index of the max element in the current window
        if (i >= k - 1) {
            result.push(nums[dq[0]]);
        }
    }
    
    return result;
};

#include <vector>
#include <deque>
using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq; // Stores indices of elements in decreasing order of value
        
        for (int i = 0; i < nums.size(); ++i) {
            // Remove indices out of the current window
            if (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }
            
            // Remove indices of elements smaller than the current element
            while (!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }
            
            dq.push_back(i);
            
            // The front of the deque is the index of the max element in the current window
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        
        return result;
    }
};

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // Stores indices
        
        for (int i = 0; i < n; i++) {
            // Remove indices out of the current window
            if (!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            
            // Remove indices of elements smaller than the current element
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            
            dq.offerLast(i);
            
            // The front of the deque is the index of the max element in the current window
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        
        return result;
    }
}

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        dq = deque() # Stores indices
        
        for i, num in enumerate(nums):
            # Remove indices out of the current window
            if dq and dq[0] <= i - k:
                dq.popleft()
            
            # Remove indices of elements smaller than the current element
            while dq and nums[dq[-1]] <= num:
                dq.pop()
            
            dq.append(i)
            
            # The front of the deque is the index of the max element in the current window
            if i >= k - 1:
                result.append(nums[dq[0]])
        
        return result

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const result = [];
    const dq = []; // Stores indices
    
    for (let i = 0; i < nums.length; i++) {
        // Remove indices out of the current window
        if (dq.length > 0 && dq[0] <= i - k) {
            dq.shift();
        }
        
        // Remove indices of elements smaller than the current element
        while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) {
            dq.pop();
        }
        
        dq.push(i);
        
        // The front of the deque is the index of the max element in the current window
        if (i >= k - 1) {
            result.push(nums[dq[0]]);
        }
    }
    
    return result;
};

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Maximum Values in Subsequences Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Sliding Window

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Maximum Values in Subsequences — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor