LeetCode Entry

239. Sliding Window Maximum

16.08.2023 medium 2023 kotlin

List of sliding window's maximums

239. Sliding Window Maximum medium blog post substack

image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/310

Problem TLDR

List of sliding window’s maximums

Intuition

To quickly find a maximum in a sliding window, consider example:

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

After each new maximum appends to the end of the window, they become the maximum until the window slides it out, so all lesser positions to the left of it are irrelevant.

Approach

We can use a decreasing Stack technique to remove all the smaller elements. However, to maintain a window size, we’ll need a Queue.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun maxSlidingWindow(nums: IntArray, k: Int): IntArray = with(ArrayDeque<Int>()) {
        val res = mutableListOf<Int>()
        nums.forEachIndexed { i, x ->
          while (isNotEmpty() && nums[peekLast()] < x) removeLast()
          add(i)
          while (isNotEmpty() && i - peekFirst() + 1 > k) removeFirst()
          if (i >= k - 1) res += nums[peekFirst()]
        }
        return res.toIntArray()
    }