Sliding Window Maximum
Program to find Maximum of all subarrays of size K (Sliding Window Maximum) Problem
You are provided with an array of integers, nums, and a positive integer, k. Imagine a sliding window of size k that begins at the far-left side of the array.
This window moves one position to the right at a time until it fully traverses the array, covering all possible subarrays of length k.
At each step of this sliding process, you need to identify and record the maximum element within the current window.
Task is to return a list containing these maximum values for each position of the sliding window.
Output: [2,2,4,4,6]
Explanation :
Window position Max
————— —–
[1 2 1] 0 4 2 6 2
1 [2 1 0] 4 2 6 2
1 2 [1 0 4] 2 6 4
1 2 1 [0 4 2] 6 4
1 2 1 0 [4 2 6] 6
Constraints:
- 1 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- 1 <= k <= nums.length
Program to find Maximum of all subarrays of size K (Sliding Window Maximum) Solution
Recommendation for Time and Space Complexity –You should aim for a solution as good or better than O(nlogn) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force solution would involve iterating through each window of size k and finding the maximum element within the window by iterating through it. This would be an O(n * k) solution. Can you think of a better way? Maybe think of a data structure that tells the current maximum element of the window in O(1) time.
Hint 2 :
A heap is the best data structure to use when dealing with maximum or minimum values and it takes O(1) time to get the max or min value. Here, we use a max-heap. But what should we do if the current maximum element is no longer part of the window? Can you think of a different way of adding values to the max-heap?
Hint 3 :
We process each window by adding elements to the heap along with their indices to track whether the maximum value is still within the current window. As we move from one window to the next, an element may go out of the window but still remain in the max-heap. Is there a way to handle this situation efficiently?
Hint 4 :
We can ignore those elements that are no longer part of the current window, except when the maximum value is outside the window. In that case, we remove elements from the max-heap until the maximum value belongs to the current window. Why? Because those elements will be eventually removed when the maximum element goes out of the window.
There are mainly 5 approach to solve this problem-
- Brute Force Method
- Segment Tree Method
- Heap Method
- Dynamic Programing Method
- Deque Method
1. Brute Force Method
Iterate through each window of size k, compute the maximum element in the window, and store it in the result. This method is simple but inefficient with a time complexity of O(n⋅k).
- Time complexity: O(n^2)
- Space complexity: O(1)
where n is the length of the array and k is the size of the window.
Code
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
vector output;
int n = nums.size();
for (int i = 0; i <= n - k; i++) {
int maxi = nums[i];
for (int j = i; j < i + k; j++) {
maxi = max(maxi, nums[j]);
}
output.push_back(maxi);
}
return output;
}
};
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] output = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
int maxi = nums[i];
for (int j = i; j < i + k; j++) {
maxi = Math.max(maxi, nums[j]);
}
output[i] = maxi;
}
return output;
}
}
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
output = []
for i in range(len(nums) - k + 1):
maxi = nums[i]
for j in range(i, i + k):
maxi = max(maxi, nums[j])
output.append(maxi)
return output
class Solution {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
maxSlidingWindow(nums, k) {
let output = [];
for (let i = 0; i <= nums.length - k; i++) {
let maxi = nums[i];
for (let j = i; j < i + k; j++) {
maxi = Math.max(maxi, nums[j]);
}
output.push(maxi);
}
return output;
}
}
2. Segment Tree Method
Construct a segment tree to efficiently find the maximum value in any range. Update the maximum value for each sliding window by querying the tree, achieving O(nlogn) time complexity.
- Time complexity: O(n logn)
- Space complexity: O(n)
Code
class Segment_tree {
public:
int n;
vector<int> A;
vector<int> tree;
const int NEG_INF = -1e9;
Segment_tree(int N, vector& a) {
this->n = N;
this->A = a;
while (__builtin_popcount(n) != 1) {
A.push_back(NEG_INF);
n++;
}
tree.resize(2 * n);
build();
}
void build() {
for (int i = 0; i < n; i++) { tree[n + i] = A[i]; } for (int i = n - 1; i > 0; --i) {
tree[i] = max(tree[i << 1], tree[i << 1 | 1]); } } void update(int i, int val) { tree[n + i] = val; for (int j = (n + i) >> 1; j >= 1; j >>= 1) {
tree[j] = max(tree[j << 1], tree[j << 1 | 1]);
}
}
int query(int l, int r) {
int res = NEG_INF;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, tree[l++]);
if (r & 1) res = max(res, tree[--r]);
}
return res;
}
};
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int n = nums.size();
Segment_tree segTree(n, nums);
vector output;
for (int i = 0; i <= n - k; i++) {
output.push_back(segTree.query(i, i + k - 1));
}
return output;
}
};
public class SegmentTree {
int n;
int[] A;
int[] tree;
final int NEG_INF = Integer.MIN_VALUE;
SegmentTree(int N, int[] a) {
this.n = N;
while (Integer.bitCount(n) != 1) {
n++;
}
A = new int[n];
for (int i = 0; i < N; i++) {
A[i] = a[i];
}
for (int i = N; i < n; i++) {
A[i] = NEG_INF;
}
tree = new int[2 * n];
build();
}
void build() {
for (int i = 0; i < n; i++) {
tree[n + i] = A[i];
}
for (int i = n - 1; i > 0; --i) {
tree[i] = Math.max(tree[i << 1], tree[i << 1 | 1]);
}
}
void update(int i, int val) {
tree[n + i] = val;
for (int j = (n + i) >> 1; j >= 1; j >>= 1) {
tree[j] = Math.max(tree[j << 1], tree[j << 1 | 1]);
}
}
int query(int l, int r) {
int res = NEG_INF;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if ((l & 1) == 1) res = Math.max(res, tree[l++]);
if ((r & 1) == 1) res = Math.max(res, tree[--r]);
}
return res;
}
}
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
SegmentTree segTree = new SegmentTree(n, nums);
int[] output = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
output[i] = segTree.query(i, i + k - 1);
}
return output;
}
}
class SegmentTree:
def __init__(self, N, a):
self.n = N
self.A = a[:]
while (self.n & (self.n - 1)) != 0:
self.A.append(float('-inf'))
self.n += 1
self.tree = [0] * (2 * self.n)
self.build()
def build(self):
for i in range(self.n):
self.tree[self.n + i] = self.A[i]
for i in range(self.n - 1, 0, -1):
self.tree[i] = max(self.tree[i << 1], self.tree[i << 1 | 1])
def update(self, i, val):
self.tree[self.n + i] = val
j = (self.n + i) >> 1
while j >= 1:
self.tree[j] = max(self.tree[j << 1], self.tree[j << 1 | 1])
j >>= 1
def query(self, l, r):
res = float('-inf')
l += self.n
r += self.n + 1
while l < r:
if l & 1:
res = max(res, self.tree[l])
l += 1
if r & 1:
r -= 1
res = max(res, self.tree[r])
l >>= 1
r >>= 1
return res
class Solution:
def maxSlidingWindow(self, nums, k):
n = len(nums)
segTree = SegmentTree(n, nums)
output = []
for i in range(n - k + 1):
output.append(segTree.query(i, i + k - 1))
return output
class SegmentTree {
/**
* @constructor
* @param {number} N
* @param {number[]} a
*/
constructor(N, a) {
this.n = N;
this.A = [...a];
this.NEG_INF = -Infinity;
while ((this.n & (this.n - 1)) !== 0) {
this.A.push(this.NEG_INF);
this.n++;
}
this.tree = new Array(2 * this.n).fill(0);
this.build();
}
build() {
for (let i = 0; i < this.n; i++) {
this.tree[this.n + i] = this.A[i];
}
for (let i = this.n - 1; i > 0; i--) {
this.tree[i] = Math.max(this.tree[i << 1], this.tree[i << 1 | 1]);
}
}
/**
* @param {number} i
* @param {number} val
*/
update(i, val) {
this.tree[this.n + i] = val;
for (let j = (this.n + i) >> 1; j >= 1; j >>= 1) {
this.tree[j] = Math.max(this.tree[j << 1], this.tree[j << 1 | 1]);
}
}
/**
* @param {number} l
* @param {number} r
* @return {number}
*/
query(l, r) {
let res = this.NEG_INF;
l += this.n;
r += this.n + 1;
while (l < r) {
if (l & 1) res = Math.max(res, this.tree[l++]);
if (r & 1) res = Math.max(res, this.tree[--r]);
l >>= 1;
r >>= 1;
}
return res;
}
}
class Solution {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
maxSlidingWindow(nums, k) {
let n = nums.length;
let segTree = new SegmentTree(n, nums);
let output = [];
for (let i = 0; i <= n - k; i++) {
output.push(segTree.query(i, i + k - 1));
}
return output;
}
}
3. Heap Method
Use a max-heap to track the maximum element in the current window. Remove elements outside the window and push new elements into the heap, maintaining the maximum in O(n logk) time complexity.
- Time complexity: O(n logn)
- Space complexity: O(n)
Code
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
priority_queue> heap;
vector output;
for (int i = 0; i < nums.size(); i++) {
heap.push({nums[i], i});
if (i >= k - 1) {
while (heap.top().second <= i - k) {
heap.pop();
}
output.push_back(heap.top().first);
}
}
return output;
}
};
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
PriorityQueue heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
int[] output = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
heap.offer(new int[]{nums[i], i});
if (i >= k - 1) {
while (heap.peek()[1] <= i - k) {
heap.poll();
}
output[idx++] = heap.peek()[0];
}
}
return output;
}
}
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
heap = []
output = []
for i in range(len(nums)):
heapq.heappush(heap, (-nums[i], i))
if i >= k - 1:
while heap[0][1] <= i - k:
heapq.heappop(heap)
output.append(-heap[0][0])
return output
class Solution {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
maxSlidingWindow(nums, k) {
const heap = new MaxPriorityQueue(x => x[0]);
const output = [];
const length = nums.length;
for (let i = 0; i < length; i++) {
heap.enqueue([nums[i], i]);
if (i >= k - 1) {
while (heap.front()[1] <= i - k) {
heap.dequeue();
}
output.push(heap.front()[0]);
}
}
return output;
}
}
4. Dynamic Programming Method
Precompute maximums for overlapping window segments in two arrays (left-to-right and right-to-left sweeps). Combine these precomputed values to get the maximum for each window in O(n).
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int n = nums.size();
vector leftMax(n);
vector rightMax(n);
leftMax[0] = nums[0];
rightMax[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
if (i % k == 0) {
leftMax[i] = nums[i];
} else {
leftMax[i] = max(leftMax[i - 1], nums[i]);
}
if ((n - 1 - i) % k == 0) {
rightMax[n - 1 - i] = nums[n - 1 - i];
} else {
rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - 1 - i]);
}
}
vector output(n - k + 1);
for (int i = 0; i < n - k + 1; i++) {
output[i] = max(leftMax[i + k - 1], rightMax[i]);
}
return output;
}
};
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = nums[0];
rightMax[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
if (i % k == 0) {
leftMax[i] = nums[i];
} else {
leftMax[i] = Math.max(leftMax[i - 1], nums[i]);
}
if ((n - 1 - i) % k == 0) {
rightMax[n - 1 - i] = nums[n - 1 - i];
} else {
rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - 1 - i]);
}
}
int[] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
output[i] = Math.max(leftMax[i + k - 1], rightMax[i]);
}
return output;
}
}
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
leftMax = [0] * n
rightMax = [0] * n
leftMax[0] = nums[0]
rightMax[n - 1] = nums[n - 1]
for i in range(1, n):
if i % k == 0:
leftMax[i] = nums[i]
else:
leftMax[i] = max(leftMax[i - 1], nums[i])
if (n - 1 - i) % k == 0:
rightMax[n - 1 - i] = nums[n - 1 - i]
else:
rightMax[n - 1 - i] = max(rightMax[n - i], nums[n - 1 - i])
output = [0] * (n - k + 1)
for i in range(n - k + 1):
output[i] = max(leftMax[i + k - 1], rightMax[i])
return output
class Solution {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
maxSlidingWindow(nums, k) {
const n = nums.length;
const leftMax = new Array(n);
const rightMax = new Array(n);
leftMax[0] = nums[0];
rightMax[n - 1] = nums[n - 1];
for (let i = 1; i < n; i++) {
if (i % k === 0) {
leftMax[i] = nums[i];
} else {
leftMax[i] = Math.max(leftMax[i - 1], nums[i]);
}
if ((n - 1 - i) % k === 0) {
rightMax[n - 1 - i] = nums[n - 1 - i];
} else {
rightMax[n - 1 - i] = Math.max(rightMax[n - i], nums[n - 1 - i]);
}
}
const output = new Array(n - k + 1);
for (let i = 0; i < n - k + 1; i++) {
output[i] = Math.max(leftMax[i + k - 1], rightMax[i]);
}
return output;
}
}
5. Deque Method
Use a deque to maintain indices of useful elements in the current window. Update the deque as the window slides, ensuring the maximum can be retrieved in O(1). This method runs in O(n) time.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int n = nums.size();
vector output(n - k + 1);
deque q;
int l = 0, r = 0;
while (r < n) {
while (!q.empty() && nums[q.back()] < nums[r]) {
q.pop_back();
}
q.push_back(r);
if (l > q.front()) {
q.pop_front();
}
if ((r + 1) >= k) {
output[l] = nums[q.front()];
l++;
}
r++;
}
return output;
}
};
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] output = new int[n - k + 1];
Deque q = new LinkedList<>();
int l = 0, r = 0;
while (r < n) {
while (!q.isEmpty() && nums[q.getLast()] < nums[r]) {
q.removeLast();
}
q.addLast(r);
if (l > q.getFirst()) {
q.removeFirst();
}
if ((r + 1) >= k) {
output[l] = nums[q.getFirst()];
l++;
}
r++;
}
return output;
}
}
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
output = []
q = deque() # index
l = r = 0
while r < len(nums):
while q and nums[q[-1]] < nums[r]:
q.pop()
q.append(r)
if l > q[0]:
q.popleft()
if (r + 1) >= k:
output.append(nums[q[0]])
l += 1
r += 1
return output
class Solution {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
maxSlidingWindow(nums, k) {
const n = nums.length;
const output = new Array(n - k + 1);
const q = new Deque();
let l = 0, r = 0;
while (r < n) {
while (q.size() && nums[q.back()] < nums[r]) {
q.popBack();
}
q.pushBack(r);
if (l > q.front()) {
q.popFront();
}
if ((r + 1) >= k) {
output[l] = nums[q.front()];
l++;
}
r++;
}
return output;
}
}
