Sliding Window Maximum

Intuition:

A naive approach to solve this problem involves considering every window possible of size K and then finding the maximum element for each window.

Approach:

Traverse on the array getting all the windows possible of size K using a for loop.
For each window, find the maximum element using a nested for loop. Store the maximums obtained in a list.
Once the traversal for all the windows is complete, return the list as answer.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to get the maximum sliding window
    vector<int> maxSlidingWindow(vector<int> &arr, int k) {
        
        int n = arr.size(); // Size of array
        
        // To store the answer
        vector<int> ans;
        
        /* Traverse on the arrary 
        for valid window */
        for(int i=0; i <= n-k; i++) {
            
            // To store the maximum of the window
            int maxi = arr[i];
            
            // Traverse the window
            for(int j=i; j < i+k; j++) {
                // Update the maximum
                maxi = max(maxi, arr[j]);
            }
            
            // Add the maximum to the result
            ans.push_back(maxi);
        }
        
        // Return the stored result
        return ans;
    }
};

int main() {
    vector<int> arr = {4, 0, -1, 3, 5, 3, 6, 8};
    int k = 3;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    maximum sliding window */
    vector<int> ans = sol.maxSlidingWindow(arr, k);
    
    cout << "The maximum elements in the sliding window are: ";
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to get the maximum sliding window
    public List<Integer> maxSlidingWindow(int[] arr, int k) {
        
        int n = arr.length; // Size of array
        
        // To store the answer
        List<Integer> ans = new ArrayList<>();
        
        /* Traverse on the arrary 
        for valid window */
        for(int i = 0; i <= n - k; i++) {
            
            // To store the maximum of the window
            int maxi = arr[i];
            
            // Traverse the window
            for(int j = i; j < i + k; j++) {
                // Update the maximum
                maxi = Math.max(maxi, arr[j]);
            }
            
            // Add the maximum to the result
            ans.add(maxi);
        }
        
        // Return the stored result
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {4, 0, -1, 3, 5, 3, 6, 8};
        int k = 3;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to get the
        maximum sliding window */
        List<Integer> ans = sol.maxSlidingWindow(arr, k);
        
        System.out.println("The maximum elements in the sliding window are: ");
        for(int num : ans) {
            System.out.print(num + " ");
        }
    }
}
class Solution:
    # Function to get the maximum sliding window
    def maxSlidingWindow(self, arr, k):
        
        n = len(arr) # Size of array
        
        # To store the answer
        ans = []
        
        # Traverse on the array for valid window
        for i in range(n - k + 1):
            
            # To store the maximum of the window
            maxi = arr[i]
            
            # Traverse the window
            for j in range(i, i + k):
                # Update the maximum
                maxi = max(maxi, arr[j])
            
            # Add the maximum to the result
            ans.append(maxi)
        
        # Return the stored result
        return ans

# Creating an instance of Solution class
sol = Solution()

arr = [4, 0, -1, 3, 5, 3, 6, 8]
k = 3

# Function call to get the maximum sliding window
ans = sol.maxSlidingWindow(arr, k)

print("The maximum elements in the sliding window are: ")
for num in ans:
    print(num, end=" ")
class Solution {
    // Function to get the maximum sliding window
    maxSlidingWindow(arr, k) {
        
        let n = arr.length; // Size of array
        
        // To store the answer
        let ans = [];
        
        /* Traverse on the arrary 
        for valid window */
        for(let i = 0; i <= n - k; i++) {
            
            // To store the maximum of the window
            let maxi = arr[i];
            
            // Traverse the window
            for(let j = i; j < i + k; j++) {
                // Update the maximum
                maxi = Math.max(maxi, arr[j]);
            }
            
            // Add the maximum to the result
            ans.push(maxi);
        }
        
        // Return the stored result
        return ans;
    }
}

let arr = [4, 0, -1, 3, 5, 3, 6, 8];
let k = 3;

/* Creating an instance of 
Solution class */
let sol = new Solution();

/* Function call to get the
maximum sliding window */
let ans = sol.maxSlidingWindow(arr, k);

console.log("The maximum elements in the sliding window are: ");
for(let num of ans) {
    console.log(num + " ");
}

Complexity Analysis:

Time Complexity: O((N-K)*K) (where N is the size of given array)
Using two nested loops.

Space Complexity: O(N-K)
Due to the size taken to return the answer.

Intuition:

In the earlier approach, scanning every element of the window repeatedly was resulting in increased time complexity. Instead, if there can be a way where the maximum element for a window can be found in constant time, the overall time complexity will improve significantly.

What is the best suitable data structure?

Every time the sliding window moves by one step, an element is added to the window and an previously added element is removed from the window. A data-structure that can push elements from one end and remove elements from the other end is queue. Every time the window moves by one step, the queue is updated to manage the current window elements.

Understanding:

The maximum element in a particular window can be found directly using the concept of monotonic queue, which includes storing the elements in a decreasing order. This way the maximum element will always be the front element in the queue which can be retrieved from the queue in constant time.
In order to maintain the decreasing order of elements in queue, before adding the new element to the queue, all the smaller elements already present in front of the queue can be popped out.

But, a queue data structure does not provide pop operation from the front. To overcome this, a Deque (Double Ended Queue) can be used, which enables efficient insertion and retrieval from both ends.

Approach:

Determine the size of the input array. Prepare a vector to store the results. Utilize a deque to maintain the indices of array elements within the current window.
For each element in the array, update the deque to maintain only the indices of elements within the current window by popping the elements from the front.
Ensure the deque maintains a monotonic decreasing order by removing indices of elements from the back that are less than or equal to the current element. Add the current element's index to the back of the deque.
Once the first window(of required size) is fully traversed, store the maximum element (located at the front of the deque) for each window position by adding the corresponding array value to the result.
Return the result that contains the maximum values for each sliding window position and is returned as the output.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to get the maximum sliding window
    vector<int> maxSlidingWindow(vector<int> &arr, int k) {
        
        int n = arr.size(); // Size of array
        
        // To store the answer
        vector<int> ans;
        
        // Deque data structure
        deque <int> dq;
        
        // Traverse the 
        for(int i=0; i < n; i++) {
            
            // Update deque to maintain current window
            if (!dq.empty() && dq.front() <= (i-k)) {
                dq.pop_front();
            }
            
            /* Maintain the monotonic (decreasing) 
            order of elements in deque */
            while (!dq.empty() && arr[dq.back()] <= arr[i]) {
                dq.pop_back();
            }
            
            // Add current elements index to the deque
            dq.push_back(i);
            
            /* Store the maximum element from 
            the first window possible */
            if (i >= (k-1)) {
                ans.push_back(arr[dq.front()]);
            }
        }
        
        // Return the stored result
        return ans;
    }
};

int main() {
    vector<int> arr = {4, 0, -1, 3, 5, 3, 6, 8};
    int k = 3;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    maximum sliding window */
    vector<int> ans = sol.maxSlidingWindow(arr, k);
    
    cout << "The maximum elements in the sliding window are: ";
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to get the maximum sliding window
    public int[] maxSlidingWindow(int[] arr, int k) {
        
        int n = arr.length; // Size of array
        
        // To store the answer
        int[] ans = new int[n - k + 1];
        int ansIndex = 0;
        
        // Deque data structure
        Deque<Integer> dq = new LinkedList<>();
        
        // Traverse the array
        for (int i = 0; i < n; i++) {
            
            // Update deque to maintain current window
            if (!dq.isEmpty() && dq.peekFirst() <= (i - k)) {
                dq.pollFirst();
            }
            
            /* Maintain the monotonic (decreasing) 
            order of elements in deque */
            while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i]) {
                dq.pollLast();
            }
            
            // Add current element's index to the deque
            dq.offerLast(i);
            
            /* Store the maximum element from 
            the first window possible */
            if (i >= (k - 1)) {
                ans[ansIndex++] = arr[dq.peekFirst()];
            }
        }
        
        // Return the stored result
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {4, 0, -1, 3, 5, 3, 6, 8};
        int k = 3;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to get the
        maximum sliding window */
        int[] ans = sol.maxSlidingWindow(arr, k);
        
        System.out.print("The maximum elements in the sliding window are: ");
        for (int i = 0; i < ans.length; i++) {
            System.out.print(ans[i] + " ");
        }
    }
}
from collections import deque

class Solution:
    # Function to get the maximum sliding window
    def maxSlidingWindow(self, arr, k):
        
        n = len(arr) # Size of array
        
        # To store the answer
        ans = []
        
        # Deque data structure
        dq = deque()
        
        # Traverse the array
        for i in range(n):
            
            # Update deque to maintain current window
            if dq and dq[0] <= (i - k):
                dq.popleft()
            
            # Maintain the monotonic (decreasing) 
            # order of elements in deque
            while dq and arr[dq[-1]] <= arr[i]:
                dq.pop()
            
            # Add current element's index to the deque
            dq.append(i)
            
            # Store the maximum element from 
            # the first window possible
            if i >= (k - 1):
                ans.append(arr[dq[0]])
        
        # Return the stored result
        return ans

# Creating an instance of Solution class
sol = Solution()

# Array and window size
arr = [4, 0, -1, 3, 5, 3, 6, 8]
k = 3

# Function call to get the maximum sliding window
ans = sol.maxSlidingWindow(arr, k)

print("The maximum elements in the sliding window are:", ans)
class Solution {
    // Function to get the maximum sliding window
    maxSlidingWindow(arr, k) {
        
        const n = arr.length; // Size of array
        
        // To store the answer
        const ans = [];
        
        // Deque data structure
        const dq = [];
        
        // Traverse the array
        for (let i = 0; i < n; i++) {
            
            // Update deque to maintain current window
            if (dq.length && dq[0] <= (i - k)) {
                dq.shift();
            }
            
            /* Maintain the monotonic (decreasing) 
            order of elements in deque */
            while (dq.length && arr[dq[dq.length - 1]] <= arr[i]) {
                dq.pop();
            }
            
            // Add current element's index to the deque
            dq.push(i);
            
            /* Store the maximum element from 
            the first window possible */
            if (i >= (k - 1)) {
                ans.push(arr[dq[0]]);
            }
        }
        
        // Return the stored result
        return ans;
    }
}

// Array and window size
const arr = [4, 0, -1, 3, 5, 3, 6, 8];
const k = 3;

/* Creating an instance of 
Solution class */
const sol = new Solution(); 

/* Function call to get the
maximum sliding window */
const ans = sol.maxSlidingWindow(arr, k);

console.log("The maximum elements in the sliding window are:", ans);

Complexity Analysis:

Time Complexity: O(N) (where N is the size of given array)

The array is traversed once taking O(N) time.
In the worst-case, each element is pushed in and popped out from deque only once taking O(N) time.

Space Complexity: O(N-K) + O(K)

The deque will store K elements at maximum, taking O(K) time.
The result list stores N-K+1 maximums taking O(N-K) space.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

What is the best suitable data structure?

Understanding:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts