Skip to main content

25. Sliding Window Maximum

hardAsked at Electronic Arts

Return the maximum of each sliding window of size k in O(n) using a monotonic deque, a technique EA uses for real-time game stat tracking and replay analysis windows.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array nums and an integer k, there is a sliding window of size k which moves from left to right. Return an array of the maximum values in each window position. You can only see the k numbers in the window.

Constraints

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

Examples

Example 1

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

Example 2

Input
nums = [1], k = 1
Output
[1]

Approaches

1. Brute force sliding window

For each window position, scan all k elements to find the max — O(n*k) and fails on large inputs.

Time
O(n*k)
Space
O(1)
function maxSlidingWindow(nums, k) {
  const res = [];
  for (let i = 0; i <= nums.length - k; i++) {
    res.push(Math.max(...nums.slice(i, i + k)));
  }
  return res;
}

Tradeoff:

2. Monotonic deque

Maintain a deque of indices in decreasing value order. Remove indices outside the window from the front, and remove smaller elements from the back before adding the current index. The front always holds the window maximum index.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const dq = [], res = [];
  for (let i = 0; i < nums.length; i++) {
    // remove out-of-window indices
    while (dq.length && dq[0] < i - k + 1) dq.shift();
    // remove smaller elements from back
    while (dq.length && nums[dq[dq.length-1]] < nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) res.push(nums[dq[0]]);
  }
  return res;
}

Tradeoff:

Electronic Arts-specific tips

EA interviews cover game development data structures, pathfinding (A*, BFS on grids), spatial algorithms, and simulation problems. Grid/matrix manipulation and BFS on 2D arrays are very common.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Sliding Window Maximum and other Electronic Arts interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →