Problem overview
The method maxSlidingWindow receives an Array[Int] named nums and a window size k. The window starts at the left end of nums and slides right one position at a time until it reaches the end. At each position it covers k neighbouring values. The method returns an array with the largest value of each window, from left to right.
For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the windows are [1, 3, -1], [3, -1, -3], [-1, -3, 5], [-3, 5, 3], [5, 3, 6] and [3, 6, 7], and their maxima are [3, 3, 5, 5, 6, 7]. An array of length n has n - k + 1 windows, so the result has that length. For [7, 2, 4] with k = 2 the answer is [7, 4]: once the 7 has left the window, 4 is the largest value.
The lesson asks for O(n) time and O(n) extra space.
Approach: keep only the values that can still win
The brute force scans all k values of every window, which costs O(n * k). With 100,000 values and a large k, that is far too slow.
Notice that many values in a window can never be the answer. Suppose a 3 sits before a 5 inside the window. The 3 leaves the window first, because it is further left, and for as long as it stays, the 5 is there too and is bigger. So the 3 can never be a maximum again and can be forgotten.
That leads to a monotonic deque: a double-ended queue holding the indexes of the candidate values, with those values decreasing from front to back. Two rules keep it correct:
- When a new value arrives, remove from the back every candidate whose value is less than or equal to it. They can never win again. Then add the new index at the back.
- When the front index has slid out of the window, remove it from the front.
The front is then always the maximum of the current window: it is the largest candidate, and every window value that isn't in the deque was dropped because something at least as big sat to its right. Every index enters the deque once and leaves it at most once, so the whole pass is O(n), whatever k is.
The deque while processing the first example, with the values it holds:
i=0 value=1 deque indexes=[0] values=[1]
i=1 value=3 deque indexes=[1] values=[3]
i=2 value=-1 deque indexes=[1,2] values=[3,-1]
i=3 value=-3 deque indexes=[1,2,3] values=[3,-1,-3]
i=4 value=5 deque indexes=[4] values=[5]
i=5 value=3 deque indexes=[4,5] values=[5,3]
i=6 value=6 deque indexes=[6] values=[6]
i=7 value=7 deque indexes=[7] values=[7]
At i=3 the front index 1 is still inside the window that starts at index 1, and the maximum is 3. At i=4 the incoming 5 clears the whole deque. Once the window is full (from i=2), the value at the front index is the window's maximum.
Step by step
- Create the deque.
mutable.ArrayDeque[Int]()in avalnamedcandidatesadds and removes at both ends in constant time. It stores indexes, not values: an index tells when an entry has left the window, andnums(index)still gives the value. - Create the result array with
Array.fill(nums.length - k + 1)(0), one slot per window. - Visit every value with
for (i <- nums.indices). On each turn,iis the right end of the window. - Drop the front if it left the window. The window now starts at
i - k + 1, so a front index ofi - kor less is outside it. Indexes are in increasing order and only one can expire per turn, so a singleifis enough. - Drop weaker candidates from the back. A
whileloop runs as long as the deque is not empty andnums(candidates.last) <= nums(i). - Remove the back inside that loop with
removeLast(). - Add the new index at the back with
append(i). It is smaller than every value left in the deque, so the values still decrease. It may become the maximum later, when the bigger values ahead of it expire. - Record the maximum once the window is full. When
i >= k - 1, storenums(candidates.head)inresult(i - k + 1). The window ending atistarts ati - k + 1, which is also its place in the result. - Return
resultas the last expression.
The solution in Scala
class Solution {
def maxSlidingWindow(nums: Array[Int], k: Int): Array[Int] = {
val candidates = mutable.ArrayDeque[Int]()
val result = Array.fill(nums.length - k + 1)(0)
for (i <- nums.indices) {
if (candidates.nonEmpty && candidates.head <= i - k) candidates.removeHead()
while (candidates.nonEmpty && nums(candidates.last) <= nums(i)) {
candidates.removeLast()
}
candidates.append(i)
if (i >= k - 1) result(i - k + 1) = nums(candidates.head)
}
result
}
}
The Scala details worth a closer look:
- The import. The lesson's editor already makes
mutableavailable. In a file of your own, addimport scala.collection.mutableat the top. ArrayDequeis the right tool. The immutableListcan't remove from its back cheaply, and a plainArrayBufferremoves from the front in linear time.mutable.ArrayDequedoeshead,last,removeHead(),removeLast()andappendin amortised constant time.nonEmptyguardsheadandlast. Callingheadorlaston an empty deque throws an exception. The&&operator stops at the first false part, so the second condition is only evaluated when the deque has something in it.- Methods called with
().removeHead()andremoveLast()change the deque and return the removed element. The solution ignores that return value. ifwith one statement, no braces. The one-line forms for the front check and for the result store are fine, as long as each controls a single statement.- Assigning into an array.
result(i - k + 1) = ...updates one element in place. The array is aval, but its contents are mutable. - The last expression returns. The method ends with
result, and noreturnkeyword is needed.
Complexity
Time: O(n). Each index is appended once and removed at most once, from either the front or the back. The inner while loop looks costly, but the total number of removals across the whole run is at most n.
Space: O(n). The result holds n - k + 1 values, and the deque holds at most k indexes. The deque's size depends on k, never beyond n.
Edge cases and common mistakes
- One element.
[1]withk = 1gives[1]. k = 1. Every window is a single value, so[1, 2, 3]gives[1, 2, 3].kequal to the length. There is one window.[9, 8, 7]withk = 3gives[9].- Equal values.
[5, 5, 5, 5]withk = 3gives[5, 5]. Removing candidates that are equal to the new value (<=, not<) is safe, because the newer copy outlives the older one. - Decreasing and increasing input.
[4, 3, 2, 1]withk = 2gives[4, 3, 2], where the deque keeps growing and the front is removed as it expires.[1, 2, 3, 4]gives[2, 3, 4], where each new value clears the deque. - Storing values instead of indexes. Without indexes, the code can't tell when the front has left the window.
- A wrong expiry test. Using
candidates.head < i - kkeeps an index that has just left, so a window can report a maximum from outside itself. - Writing results too early. Before
ireachesk - 1the window isn't full yet. Storing then would use a negative result index and crash.
Testing
nums = [1, 3, -1, -3, 5, 3, 6, 7],k = 3gives[3, 3, 5, 5, 6, 7].nums = [1],k = 1gives[1].nums = [7, 2, 4],k = 2gives[7, 4].nums = [4, 3, 2, 1],k = 2gives[4, 3, 2].nums = [1, 2, 3, 4],k = 2gives[2, 3, 4].nums = [5, 5, 5, 5],k = 3gives[5, 5].nums = [9, 8, 7],k = 3gives[9].
