Consecutive Maximum Values — Problem Statement & Solution Guide

Sliding WindowHardSliding Window / Monotonic Deque

TimeO(n)

SpaceO(k)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Sliding Window and solve the Consecutive Maximum Values problem optimally.

TopicSliding Window

PatternSliding Window / Monotonic Deque

TimeO(n)

SpaceO(k)

Problem Description

Given an integer array values and a positive integer windowSize, produce an array result such that result[i] equals the greatest element among values[i], values[i+1], …, values[i+windowSize‑1] for every valid starting index i. If windowSize is larger than values.length, the function returns an empty array. The implementation must verify that each entry of values is an integer; encountering a non‑integer should trigger an error/exception.

DSA Pattern Breakdown

"Consecutive Maximum Values"

hard

WHY DOES IT MATTER?

Sliding‑window patterns appear in time‑series analysis, rate‑limiting, and real‑time monitoring where you need aggregate statistics over recent data without re‑scanning the entire history.

OPTIMIZATION CHALLENGE

The key insight is that each element only enters and leaves the deque once, turning a potentially quadratic scan into a linear pass by exploiting the monotonic property of the deque.

REAL-WORLD CONNECTION

Think of a moving average sensor in an IoT device: as new readings arrive, the device discards the oldest reading and updates the aggregate instantly, similar to how the deque discards out‑of‑range indices and keeps the current maximum ready.

When coding, always guard the deque front against stale indices before reading the maximum; a single misplaced pop can cause off‑by‑one bugs that are hard to spot in interviews.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The problem is a classic sliding‑window maximum. For each contiguous sub‑array of length k we must report the largest element. A naïve solution recomputes the maximum for every window, leading to O(n·k) time, which quickly becomes prohibitive when n and k are large (e.g., n = 10⁶, k ≈ 10⁵). The optimal paradigm treats the window as a moving frontier and maintains a data structure that can answer “what is the current maximum?” in O(1) while supporting O(1) amortized updates as the window slides. The deque (double‑ended queue) stores indices of elements in decreasing order; the front always holds the index of the maximum for the current window, and elements that fall out of the window or are smaller than the incoming element are discarded, guaranteeing each array entry is pushed and popped at most once.

Interview Questions on This Problem

Q1How would you compute the maximum of every sliding window of size k in O(n) time?

Use a monotonic decreasing deque to store indices. For each index i, remove indices out of the current window from the front, pop smaller values from the back, then push i. The front of the deque is the maximum for the window ending at i.

Q2What modifications are needed if the window size can be larger than the array length?

If k > n, the specification requires returning an empty array, so you check this condition up front and skip the sliding‑window logic.

Q3Can you adapt the algorithm to also return the minimum of each window without increasing asymptotic complexity?

Yes, run a second monotonic increasing deque in parallel; each deque maintains its own order, and both can be updated in O(1) amortized per element, still yielding O(n) total time and O(k) extra space.

Examples

Example 1

Input

{"values":[2,1,5,3,4],"windowSize":3}

Output

[5,5,5]

Explanation: The three windows of size 3 are [2,1,5] → max 5, [1,5,3] → max 5, and [5,3,4] → max 5, so the result is [5,5,5].

Example 2

Input

{"values":[9,-1,7,8,2,6],"windowSize":2}

Output

[9,7,8,8,6]

Explanation: Sliding windows of length 2 are: [9,‑1]→9, [‑1,7]→7, [7,8]→8, [8,2]→8, [2,6]→6. Collecting the maxima yields [9,7,8,8,6].

Example 3

Input

{"values":[5,5,5,5],"windowSize":4}

Output

[5]

Explanation: Only one window of size 4 exists – the whole array – whose maximum is 5, so the output contains a single element.

Example 4

Input

{"values":[3,1,4,1,5,9,2],"windowSize":5}

Output

[5,9,9]

Explanation: The windows are [3,1,4,1,5]→5, [1,4,1,5,9]→9, and [4,1,5,9,2]→9; thus the result is [5,9,9].

Constraints

1 <= values.length <= 10^5
1 <= windowSize <= values.length
-10^9 <= values[i] <= 10^9
All elements of values are integers

Optimal Approach & Strategy

Maintain a monotonic decreasing deque of indices while iterating once over the array; update the deque for each new element and record the front as the window maximum. This yields O(n) time and O(k) auxiliary space.

Brute Force Approach

For each starting index i compute the maximum by scanning the next k elements, storing the result, and repeat for all i. This requires O(n·k) time and O(1) extra space.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} values
 * @param {number} windowSize
 * @return {number[]}
 */
function consecutiveMaximumValues(values, windowSize) {
    const n = values.length;
    
    // Edge case: windowSize is larger than array length or invalid
    if (windowSize > n || windowSize <= 0 || n === 0) {
        return [];
    }

    const result = [];
    const dq = []; // Deque to store indices

    for (let i = 0; i < n; i++) {
        // Remove indices that are out of the current window
        if (dq.length > 0 && dq[0] <= i - windowSize) {
            dq.shift();
        }

        // Remove indices whose corresponding values are less than or equal to current value
        while (dq.length > 0 && values[dq[dq.length - 1]] <= values[i]) {
            dq.pop();
        }

        dq.push(i);

        // The front of the deque is the index of the maximum value in the current window
        if (i >= windowSize - 1) {
            result.push(values[dq[0]]);
        }
    }

    return result;
}

// Driver code for testing
const values = [2, 1, 5, 3, 4];
const windowSize = 3;
const result = consecutiveMaximumValues(values, windowSize);
console.log(JSON.stringify(result));

#include <iostream>
#include <vector>
#include <deque>
#include <stdexcept>

std::vector<int> consecutiveMaximumValues(const std::vector<int>& values, int windowSize) {
    int n = values.size();
    
    // Edge case: windowSize is larger than array length or invalid
    if (windowSize > n || windowSize <= 0 || n == 0) {
        return {};
    }

    std::vector<int> result;
    std::deque<int> dq; // Deque to store indices

    for (int i = 0; i < n; ++i) {
        // Remove indices that are out of the current window
        if (!dq.empty() && dq.front() <= i - windowSize) {
            dq.pop_front();
        }

        // Remove indices whose corresponding values are less than or equal to current value
        while (!dq.empty() && values[dq.back()] <= values[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // The front of the deque is the index of the maximum value in the current window
        if (i >= windowSize - 1) {
            result.push_back(values[dq.front()]);
        }
    }

    return result;
}

int main() {
    // Driver code for testing
    std::vector<int> values = {2, 1, 5, 3, 4};
    int windowSize = 3;

    std::vector<int> result = consecutiveMaximumValues(values, windowSize);

    std::cout << "[";
    for (size_t i = 0; i < result.size(); ++i) {
        std::cout << result[i];
        if (i < result.size() - 1) std::cout << ", ";
    }
    std::cout << "]" << std::endl;

    return 0;
}

import java.util.*;

public class Solution {
    public static List<Integer> consecutiveMaximumValues(List<Integer> values, int windowSize) {
        int n = values.size();
        
        // Edge case: windowSize is larger than array length or invalid
        if (windowSize > n || windowSize <= 0 || n == 0) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        Deque<Integer> dq = new ArrayDeque<>(); // Deque to store indices

        for (int i = 0; i < n; i++) {
            // Remove indices that are out of the current window
            if (!dq.isEmpty() && dq.peekFirst() <= i - windowSize) {
                dq.pollFirst();
            }

            // Remove indices whose corresponding values are less than or equal to current value
            while (!dq.isEmpty() && values.get(dq.peekLast()) <= values.get(i)) {
                dq.pollLast();
            }

            dq.offerLast(i);

            // The front of the deque is the index of the maximum value in the current window
            if (i >= windowSize - 1) {
                result.add(values.get(dq.peekFirst()));
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // Driver code for testing
        List<Integer> values = Arrays.asList(2, 1, 5, 3, 4);
        int windowSize = 3;

        List<Integer> result = consecutiveMaximumValues(values, windowSize);

        System.out.println(result.toString());
    }
}

from typing import List
from collections import deque

def consecutiveMaximumValues(values: List[int], windowSize: int) -> List[int]:
    n = len(values)
    
    # Edge case: windowSize is larger than array length or invalid
    if windowSize > n or windowSize <= 0 or n == 0:
        return []

    result = []
    dq = deque() # Deque to store indices

    for i in range(n):
        # Remove indices that are out of the current window
        if dq and dq[0] <= i - windowSize:
            dq.popleft()

        # Remove indices whose corresponding values are less than or equal to current value
        while dq and values[dq[-1]] <= values[i]:
            dq.pop()

        dq.append(i)

        # The front of the deque is the index of the maximum value in the current window
        if i >= windowSize - 1:
            result.append(values[dq[0]])

    return result

# Driver code for testing
if __name__ == "__main__":
    values = [2, 1, 5, 3, 4]
    windowSize = 3
    result = consecutiveMaximumValues(values, windowSize)
    print(result)

/**
 * @param {number[]} values
 * @param {number} windowSize
 * @return {number[]}
 */
function consecutiveMaximumValues(values, windowSize) {
    const n = values.length;
    
    // Edge case: windowSize is larger than array length or invalid
    if (windowSize > n || windowSize <= 0 || n === 0) {
        return [];
    }

    const result = [];
    const dq = []; // Deque to store indices

    for (let i = 0; i < n; i++) {
        // Remove indices that are out of the current window
        if (dq.length > 0 && dq[0] <= i - windowSize) {
            dq.shift();
        }

        // Remove indices whose corresponding values are less than or equal to current value
        while (dq.length > 0 && values[dq[dq.length - 1]] <= values[i]) {
            dq.pop();
        }

        dq.push(i);

        // The front of the deque is the index of the maximum value in the current window
        if (i >= windowSize - 1) {
            result.push(values[dq[0]]);
        }
    }

    return result;
}

// Driver code for testing
const values = [2, 1, 5, 3, 4];
const windowSize = 3;
const result = consecutiveMaximumValues(values, windowSize);
console.log(JSON.stringify(result));

Asked in Top Tech Interviews

Cred

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.