Skip to main content

25. Sliding Window Maximum

hardAsked at PayPal

Return the maximum value in every sliding window of size k over an array in O(n) time. PayPal uses this deque-based problem to test candidates on streaming aggregation — a core primitive in real-time fraud scoring and transaction risk-window analysis.

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

Source citations

Public interview reports confirming this problem appears in PayPal loops.

  • Glassdoor (2025)— PayPal senior engineer reported sliding window maximum in the algorithmic design round
  • Blind (2026)— PayPal hard-problem thread cites monotonic deque as a skill tested in senior SWE onsites

Problem

You are given an array of integers nums and an integer k. There is a sliding window of size k moving from the left edge of the array to the right edge. You can only see the k numbers in the window. Each time the sliding window moves right by one position, return the max value in the window. Return the array of maximum values for each window position.

Constraints

  • 1 <= nums.length <= 100000
  • -10000 <= nums[i] <= 10000
  • 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]

Explanation: Windows: [1,3,-1]->3, [3,-1,-3]->3, [-1,-3,5]->5, [-3,5,3]->5, [5,3,6]->6, [3,6,7]->7

Example 2

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

Approaches

1. Brute force (scan each window)

For each of the n-k+1 windows, scan all k elements to find the maximum.

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

Tradeoff: O(nk) — TLE for n=100k, k=50k. Always start with this to establish the problem, then optimize.

2. Monotonic deque

Maintain a double-ended queue of indices where nums values are in decreasing order. When adding a new element, pop from the back any indices whose values are smaller (they can never be the max while the new element is in the window). Pop from the front when the front index falls outside the window. The front is always the current window maximum.

Time
O(n)
Space
O(k)
function maxSlidingWindow(nums, k) {
  const result = [];
  const deque = []; // stores indices, values decreasing from front to back

  for (let i = 0; i < nums.length; i++) {
    // Remove indices that are out of the current window
    while (deque.length && deque[0] < i - k + 1) {
      deque.shift();
    }
    // Remove indices from the back whose values are less than nums[i]
    // (they can never be the max while nums[i] is in the window)
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    deque.push(i);

    // Start recording results once the first full window is formed
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Tradeoff: Each element is added and removed from the deque at most once — O(n) total. At PayPal, frame this as maintaining a 'current max transaction risk score' over a rolling time window without rescanning historical data.

PayPal-specific tips

PayPal interviews focus on payment processing, fraud detection logic, financial reconciliation algorithms, and distributed transaction design. Hash maps, sliding windows, and two-pointer techniques appear frequently.

Common mistakes

  • Storing values in the deque instead of indices — you need indices to check whether the front is out of the window
  • Using strict less-than in the back-pop condition: should pop when nums[back] < nums[i] (or <= if you want to keep the most recent of equals)
  • Off-by-one in the window boundary check: front is out when deque[0] < i - k + 1, not i - k

Follow-up questions

An interviewer at PayPal may pivot to one of these next:

  • Sliding window minimum — identical approach, flip the comparison direction
  • Find the maximum sum of any contiguous subarray of length exactly k
  • Given a stream with deletions and insertions, maintain a sliding window maximum with a segment tree or ordered set

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why store indices and not values in the deque?

The window validity check requires knowing whether the front element has exited the window. You can only do this if you know its original position (index). Values don't carry position information.

Why is each element processed O(1) amortized?

Each index is pushed into the deque once and popped at most once (either from the back when a larger element arrives, or from the front when it exits the window). Total operations across all n elements = O(n).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →