Introduction

The SPOJ ARRAYSUB problem asks for the maximum element in every contiguous subarray of size k. The important part of the problem is not just finding the maximums, but doing it fast enough: the correct competitive-programming approach is a deque-based sliding window in linear time.

Why the naive approach is too slow

A direct solution checks every window of size k and scans all k elements to find its maximum.

That costs O(n * k), which is too slow when the array is large.

The key optimization is to avoid recomputing window maximums from scratch.

The deque idea

Use a deque to store indices of elements that are still relevant for the current window.

The deque maintains two invariants:

• indices are kept in increasing order from front to back
• values at those indices are kept in decreasing order

That means the front of the deque always points to the maximum element for the current window.

How the update works

When you process a new element at index i:

1. remove indices from the front if they are outside the current window
2. remove indices from the back while their values are less than or equal to the new value
3. append the new index
4. once the first full window is formed, output the value at the front index

Every index enters the deque once and leaves it at most once, which is why the total cost is O(n).

Python implementation

Here is a standard solution.

1from collections import deque
2
3
4def sliding_window_max(arr, k):
5    dq = deque()
6    result = []
7
8    for i, value in enumerate(arr):
9        while dq and dq[0] <= i - k:
10            dq.popleft()
11
12        while dq and arr[dq[-1]] <= value:
13            dq.pop()
14
15        dq.append(i)
16
17        if i >= k - 1:
18            result.append(arr[dq[0]])
19
20    return result
21
22
23arr = [10, 5, 2, 7, 8, 7]
24print(sliding_window_max(arr, 3))

For this input, the output is [10, 7, 8, 8].

Why the complexity is linear

The trickiest part of the analysis is realizing that the inner while loops do not make the algorithm quadratic.

Each index can be:

• appended once
• popped from the back at most once
• popped from the front at most once

So even though the code contains nested-looking loops, the total number of deque operations across the whole array is proportional to n.

This is an amortized O(n) argument.

Why storing indices matters

You must store indices rather than raw values because the algorithm needs to know when an element falls out of the window.

If you only stored values, you would not know whether the front element still belongs to the current subarray.

Indices solve both problems at once:

• they let you compare values through arr[index]
• they let you remove expired entries with i - k

Edge cases to remember

A few edge cases still matter in implementation:

• 'k = 1, every element is its own window maximum'
• duplicate values, where using <= or < changes which index survives
• very large inputs, where fast input and output may matter in C++ or Java

In Python, the deque logic is still fine, but competitive-programming input handling may need attention for maximum constraints.

Common Pitfalls

A common mistake is storing values instead of indices and then failing to remove expired window entries correctly.

Another issue is misunderstanding the time complexity because of the while loops. The algorithm is linear overall, not quadratic.

It is also easy to get the window-expiration condition wrong. The front should be removed when its index is <= i - k.

Summary

• 'ARRAYSUB is a sliding-window maximum problem.'
• The efficient solution uses a deque of indices, not a repeated scan of each window.
• The deque keeps candidates in decreasing value order, so the maximum stays at the front.
• Each index is added and removed at most once, giving O(n) time.
• The main implementation risks are wrong expiration logic and storing values instead of indices.