Problem

Given an integer array nums and a window size k (sometimes denoted w), return an array containing the minimum value in every contiguous subarray (window) of size k as the window slides from left to right. If k > len(nums), return an empty list.

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [-1,-3,-3,3,3,3]

Explanation:
Window [1,3,-1] -> -1
[3,-1,-3] -> -3
[-1,-3,5] -> -3
[-3,5,3] -> 3
[5,3,6] -> 3
[3,6,7] -> 3

Constraints and edge cases

  • 1 <= k <= len(nums) for typical inputs; if k == 1 the result is each element.
  • If k > len(nums) return an empty list.
Similar Problems

Solution

Three common approaches are shown below, increasing in efficiency.

Method 1 - Brute Force

Intuition

For each window start index i, scan the next k elements and compute the minimum. This is simple but repeats work across overlapping windows.

Approach

  • For every i from 0 to n-k:
    • Compute the minimum of nums[i] through nums[i+k-1] by scanning those k elements.
    • Append that minimum to ans.
  • If k > n return an empty ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
 public:
  vector<int> slidingWindowMin(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> ans;
    if (k > n) return ans;
    for (int i = 0; i <= n - k; ++i) {
      int mn = nums[i];
      for (int j = i + 1; j < i + k; ++j) mn = std::min(mn, nums[j]);
      ans.push_back(mn);
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

package main

func slidingWindowMin(nums []int, k int) []int {
  n := len(nums)
  if k > n { return []int{} }
  ans := make([]int, 0, n-k+1)
  for i := 0; i <= n-k; i++ {
    mn := nums[i]
    for j := i+1; j < i+k; j++ {
      if nums[j] < mn { mn = nums[j] }
    }
    ans = append(ans, mn)
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int[] slidingWindowMin(int[] nums, int k) {
        int n = nums.length;
        if (k > n) return new int[0];
        int[] ans = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i <= n - k; i++) {
            int mn = nums[i];
            for (int j = i + 1; j < i + k; j++) mn = Math.min(mn, nums[j]);
            ans[idx++] = mn;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def sliding_window_min(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        if k > n:
            return []
        ans: list[int] = []
        for i in range(0, n - k + 1):
            mn = nums[i]
            for j in range(i+1, i+k):
                if nums[j] < mn:
                    mn = nums[j]
            ans.append(mn)
        return ans

Complexity

  • ⏰ Time complexity: O(n*k), because each of the O(n) windows may scan up to k elements.
  • 🧺 Space complexity: O(n-k+1) for the output ans (ignoring input).

Method 2 - DP / Block Method (Prefix/Suffix minima)

Intuition

Divide the array into blocks of size k and precompute minima from left and right within each block. For any window starting at i, the minimum is min(rightMin[i], leftMin[i+k-1]).

Approach

  • Build arrays leftMin and rightMin of length n.
  • leftMin[i] is the minimum of the block beginning at its block start up to i (left-to-right pass).
  • rightMin[i] is the minimum from i to the end of the block (right-to-left pass).
  • For each window starting at i, minimum is min(rightMin[i], leftMin[i+k-1]).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
 public:
  vector<int> slidingWindowMinDP(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> ans;
    if (k > n) return ans;
    vector<int> left(n), right(n);
    for (int i = 0; i < n; ++i) {
      if (i % k == 0) left[i] = nums[i];
      else left[i] = std::min(left[i-1], nums[i]);
    }
    for (int j = n - 1; j >= 0; --j) {
      if (j == n - 1 || (j + 1) % k == 0) right[j] = nums[j];
      else right[j] = std::min(right[j+1], nums[j]);
    }
    for (int i = 0; i + k <= n; ++i) ans.push_back(std::min(right[i], left[i + k - 1]));
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

package main

func slidingWindowMinDP(nums []int, k int) []int {
  n := len(nums)
  if k > n { return []int{} }
  left := make([]int, n)
  right := make([]int, n)
  for i := 0; i < n; i++ {
    if i%k == 0 { left[i] = nums[i] }
    else if nums[i] < left[i-1] { left[i] = nums[i] }
    else { left[i] = left[i-1] }
  }
  for j := n-1; j >= 0; j-- {
    if j == n-1 || (j+1)%k == 0 { right[j] = nums[j] }
    else if nums[j] < right[j+1] { right[j] = nums[j] }
    else { right[j] = right[j+1] }
  }
  ans := make([]int, 0, n-k+1)
  for i := 0; i + k <= n; i++ {
    if right[i] < left[i+k-1] { ans = append(ans, right[i]) }
    else { ans = append(ans, left[i+k-1]) }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[] slidingWindowMinDP(int[] nums, int k) {
        int n = nums.length;
        if (k > n) return new int[0];
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 0; i < n; i++) {
            if (i % k == 0) left[i] = nums[i];
            else left[i] = Math.min(left[i-1], nums[i]);
        }
        for (int j = n-1; j >= 0; j--) {
            if (j == n-1 || (j+1) % k == 0) right[j] = nums[j];
            else right[j] = Math.min(right[j+1], nums[j]);
        }
        int[] ans = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i + k <= n; i++) ans[idx++] = Math.min(right[i], left[i + k - 1]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def sliding_window_min_dp(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        if k > n:
            return []
        left = [0] * n
        right = [0] * n
        for i in range(n):
            if i % k == 0:
                left[i] = nums[i]
            else:
                left[i] = min(left[i-1], nums[i])
        for j in range(n-1, -1, -1):
            if j == n-1 or (j+1) % k == 0:
                right[j] = nums[j]
            else:
                right[j] = min(right[j+1], nums[j])
        ans: list[int] = []
        for i in range(0, n - k + 1):
            ans.append(min(right[i], left[i + k - 1]))
        return ans

Complexity

  • ⏰ Time complexity: O(n) — building left/right and computing outputs is linear.
  • 🧺 Space complexity: O(n) for left and right arrays plus output.

Method 3 - Monotonic Increasing Deque (Optimal)

Intuition

Maintain a deque of indices whose corresponding values are in non-decreasing order. The front of the deque holds the index of the minimum in the current window.

Approach

  • Use a deque dq that stores indices of nums in increasing order of their values.
  • Iterate r from 0 to n-1:
    • While dq not empty and nums[r] <= nums[dq.back()], pop back.
    • Append r to dq.
    • If dq.front() is < r - k + 1, pop front (index left the window).
    • When r >= k-1, append nums[dq.front()] to ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <deque>

class Solution {
 public:
  vector<int> slidingWindowMinDeque(const vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> ans;
    if (k > n) return ans;
    deque<int> dq; // indices of potential minima
    for (int r = 0; r < n; ++r) {
      while (!dq.empty() && nums[r] <= nums[dq.back()]) dq.pop_back();
      dq.push_back(r);
      if (dq.front() < r - k + 1) dq.pop_front();
      if (r >= k - 1) ans.push_back(nums[dq.front()]);
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

package main

func slidingWindowMinDeque(nums []int, k int) []int {
  n := len(nums)
  if k > n { return []int{} }
  ans := make([]int, 0, n-k+1)
  dq := make([]int, 0) // store indices
  for r := 0; r < n; r++ {
    for len(dq) > 0 && nums[r] <= nums[dq[len(dq)-1]] { dq = dq[:len(dq)-1] }
    dq = append(dq, r)
    if dq[0] < r - k + 1 { dq = dq[1:] }
    if r >= k-1 { ans = append(ans, nums[dq[0]]) }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] slidingWindowMinDeque(int[] nums, int k) {
        int n = nums.length;
        if (k > n) return new int[0];
        int[] ans = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        int idx = 0;
        for (int r = 0; r < n; r++) {
            while (!dq.isEmpty() && nums[r] <= nums[dq.peekLast()]) dq.removeLast();
            dq.addLast(r);
            if (dq.peekFirst() < r - k + 1) dq.removeFirst();
            if (r >= k - 1) ans[idx++] = nums[dq.peekFirst()];
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from collections import deque

class Solution:
    def sliding_window_min_deque(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        if k > n:
            return []
        ans: list[int] = []
        dq: deque[int] = deque()
        for r in range(n):
            while dq and nums[r] <= nums[dq[-1]]:
                dq.pop()
            dq.append(r)
            if dq[0] < r - k + 1:
                dq.popleft()
            if r >= k - 1:
                ans.append(nums[dq[0]])
        return ans

Complexity

  • ⏰ Time complexity: O(n) — each index enters and leaves the deque at most once.
  • 🧺 Space complexity: O(k) for the deque plus O(n-k+1) output.