Start learning free

LESSON 399 OF 573 · SLIDING WINDOW

Sliding Window Maximum in Kotlin: O(n) with a Monotonic Deque

Practice O(n) Read the full explanation

You are given an array of integers nums and an integer k. A window of size k starts at the left end of nums and slides to the right one position at a time, until it reaches the right end. At each position, the window covers k neighbouring values.

Return an array with the largest value of each window, from left to right.

 

Example 1:

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation:
Window position                Max
---------------                ---
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]
Explanation: There is one window, and it holds the only value.

Example 3:

Input: nums = [7, 2, 4], k = 2
Output: [7, 4]
Explanation: The windows are [7, 2] and [2, 4]. Once 7 has left the window, 4 is the largest value.

 

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

Note:

Your algorithm should run in O(n) time, where n is the length of nums, and use O(n) extra space. Finding each window's maximum from scratch takes O(n · k) time, too slow for the largest tests.

STEP 1 OF 9
    Ctrl + Enter to check

    KOTLIN · SLIDING WINDOW

    Sliding Window Maximum in Kotlin, explained

    Problem overview

    You get an IntArray nums and a window size k. A window of k neighbouring values starts at the left end and slides one position to the right at a time until it reaches the right end. The method returns an IntArray with the largest value of every window, from left to right. An array of n values has n - k + 1 windows.

    For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3 the answer is [3, 3, 5, 5, 6, 7]. For [7, 2, 4] and k = 2 it is [7, 4]: once the 7 has left the window, the 4 is the largest value.

    Approach

    The brute force scans the k values of each window to find the maximum. That takes O(n · k) time, and with 100,000 values and a large k it is too slow. Two windows next to each other share k - 1 values, so most of that work is repeated.

    The lesson keeps a deque (a queue that works at both ends) of indexes, called candidates. It holds the values that can still become the maximum of a window, and the values they point to always decrease from the front to the back. Three rules keep it that way:

    • Old entries leave at the front. The oldest index sits at the front. When it falls outside the window, it is removed.
    • Weak entries leave at the back. When a new value nums[i] arrives, every value at the back that is not bigger than it is removed. Such a value is older than nums[i], so it leaves the window first, and as long as it stays, nums[i] is there too and at least as large. It can never be a maximum again.
    • The front is the answer. The values decrease from front to back, so the front is the largest value of the window.

    Each index is added once and removed at most once, so the total work is O(n), however big k is. Storing indexes, not values, is what lets us tell when an entry has slid out of the window.

    Step by step

    1. The deque. Create val candidates = ArrayDeque<Int>(). Kotlin's ArrayDeque adds and removes at both ends in constant time.
    2. The result. Create val result = IntArray(nums.size - k + 1), one slot for each window.
    3. The loop. Loop i over nums.indices. Each turn, i is the right end of the window: the window is the k values that end at index i.
    4. Drop the front if it left the window. The window starts at i - k + 1, so an index of i - k or less is outside it. Indexes arrive in increasing order, and only one index leaves per turn, so a single if is enough: when candidates is not empty and candidates.first() <= i - k, call removeFirst().
    5. Drop weak entries from the back. A while loop runs while candidates is not empty and nums[candidates.last()] <= nums[i].
    6. Remove them. Inside that loop, call candidates.removeLast().
    7. Add the new index with candidates.addLast(i). The values left in the deque are all bigger than nums[i], so they still decrease.
    8. Record the maximum. Once the window is full, i >= k - 1, the front is its maximum: result[i - k + 1] = nums[candidates.first()]. The window that ends at i starts at i - k + 1, which is also its place in result.
    9. Return result after the loop.

    The solution in Kotlin

    class Solution {
    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
        val candidates = ArrayDeque<Int>()
        val result = IntArray(nums.size - k + 1)
        for (i in nums.indices) {
            if (candidates.isNotEmpty() && candidates.first() <= i - k) candidates.removeFirst()
            while (candidates.isNotEmpty() && nums[candidates.last()] <= nums[i]) {
                candidates.removeLast()
            }
            candidates.addLast(i)
            if (i >= k - 1) result[i - k + 1] = nums[candidates.first()]
        }
        return result
    }
}

    Kotlin details:

    • ArrayDeque here is kotlin.collections.ArrayDeque, which Kotlin imports automatically. It is not java.util.ArrayDeque. It has first(), last(), addLast, removeFirst() and removeLast().
    • first() and last() throw an exception on an empty deque, which is why each use is guarded by isNotEmpty(). The && stops at the first false part, so the second half is not evaluated for an empty deque.
    • ArrayDeque<Int> holds boxed Integer objects, while nums and result are primitive IntArrays. That is fine at this size.
    • removeLast() returns the removed value; the loop ignores it.
    • The result is an IntArray, so print it with toList() or contentToString() to see the numbers.

    A trace

    For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, printing the deque after each turn gives the indexes, the values they point to, and the window maximum (a dash while the window is not full yet):

    i=0 nums[i]=1 deque(indexes)=[0] values=[1] max=-
i=1 nums[i]=3 deque(indexes)=[1] values=[3] max=-
i=2 nums[i]=-1 deque(indexes)=[1, 2] values=[3, -1] max=3
i=3 nums[i]=-3 deque(indexes)=[1, 2, 3] values=[3, -1, -3] max=3
i=4 nums[i]=5 deque(indexes)=[4] values=[5] max=5
i=5 nums[i]=3 deque(indexes)=[4, 5] values=[5, 3] max=5
i=6 nums[i]=6 deque(indexes)=[6] values=[6] max=6
i=7 nums[i]=7 deque(indexes)=[7] values=[7] max=7

    At i=1 the 3 removes the 1, because it is bigger and arrived later. At i=4 the 5 removes everything: index 1 has just left the window, and the 5 beats the -1 and -3. The deque is always decreasing, and its front is the maximum.

    Complexity

    Time: O(n). The outer loop runs n times. The inner while loop looks like extra work per turn, but every index is added once and removed at most once, so all the removals together are at most n.

    Space: O(n). The result has n - k + 1 entries, and the deque holds at most k indexes.

    Edge cases and common mistakes

    • Using < instead of <= in the back check. Equal values would then stay in the deque. With <= an equal older value is dropped, which is safe because the newer one lasts longer. For [4, 4, 4, 4] and k = 2 the deque holds just one index after every turn, and the result is [4, 4, 4].
    • Storing values instead of indexes. You could not tell when the front has left the window.
    • Using i - k + 1 for the leaving test. The test is first() <= i - k: the window starts at i - k + 1, and anything before that is out.
    • Writing results too early. Before i reaches k - 1 the window is not full, and nothing is recorded; the first answer goes to result[0].
    • Empty-deque calls. Calling first() or last() without the isNotEmpty() check throws an exception.
    • Special sizes. With k = 1 every value is its own window: [3, 1, 2] gives [3, 1, 2]. With k = nums.size there is one window: [9, 1, 8] with k = 3 gives [9].

    Testing

    These calls were run against the solution above:

    numskResult
    [1, 3, -1, -3, 5, 3, 6, 7]3[3, 3, 5, 5, 6, 7]
    [1]1[1]
    [7, 2, 4]2[7, 4]
    [5, 4, 3, 2, 1]3[5, 4, 3]
    [1, 2, 3, 4, 5]3[3, 4, 5]
    [4, 4, 4, 4]2[4, 4, 4]
    [3, 1, 2]1[3, 1, 2]
    [9, 1, 8]3[9]
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free