Solution: Edge Cases and Cost

Here is the solution again:

public static int[] slidingMaximum(int[] values, int k) {
  int[] answer = new int[values.length - k + 1];
  Deque<Integer> candidates = new ArrayDeque<>();

  for (int i = 0; i < values.length; i++) {
    // Remove candidates that are no longer in the window.
    while (!candidates.isEmpty() && candidates.getFirst() <= i - k) {
      candidates.removeFirst();
    }

    // Remove candidates that the new value makes useless.
    while (!candidates.isEmpty()
        && values[candidates.getLast()] <= values[i]) {
      candidates.removeLast();
    }

    candidates.addLast(i);

    // The front is the maximum once the first full window exists.
    if (i >= k - 1) {
      answer[i - k + 1] = values[candidates.getFirst()];
    }
  }

  return answer;
}

What does this cost? The nested while loops might look expensive. But an index can only be added to the deque once. After that, it can be removed at most once: either from the front because it expires, or from the back because a newer value dominates it. Once removed, it never comes back.

So across the whole run:

• There are $n$ calls to addLast, one per index.
• There are at most $n$ removals total.
• Every check and array lookup around those deque operations is constant-time.

That makes the total running time $O(n)$, which is what the problem asked for.

The space is $O(k)$. The deque never needs to hold indices outside the current window, because expired indices are removed from the front. It often holds fewer than k candidates. The worst case is when the values are strictly decreasing:

values = [9, 8, 7, 6, 5], k = 5

No new value evicts an older one, so the deque holds all k indices in the window.