Maximum of all subarrays of size K using Set

Maximum of all subarrays of size K using Max-Heap:

Maximum of all subarrays of size K using Deque:

To reduce the auxilary space to O(K), Set Data Structure can be used which allows deletion of any element in O(logn N) time. Thus the size of set will never exceed K, if we delete delete the (i-Kt)h element from the Set while traversing.

Follow the given steps to solve the problem:

Create a Set to store and find the maximum element.
Traverse through the array from start to end.
Insert the element in theSet.
If the loop counter is greater than or equal to k then delete the i-Kth element from the Set.
Print the maximum element of the Set.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum element in each sliding
// window of size k
vector<int> maxSlidingWindow(vector<int>& arr, int k)
{
    vector<int> ans;
    set<pair<int, int>, greater<pair<int,int>>> st;
 
    // Initialize the set with the first k elements
    for (int i = 0; i < k; i++)
        st.insert({ arr[i], i });
 
    // The maximum element in the first window
    ans.push_back((st.begin())->first);
 
    // Process the remaining elements
    for (int i = k; i < arr.size(); i++) {
 
        // Add the current element to the set
        st.insert({ arr[i], i });
 
        // Remove the (i-k)th element from the window
        st.erase({ arr[i - k], (i - k) });
 
        // The maximum element in the current window
        ans.push_back(st.begin()->first);
    }
 
    return ans;
}
 
int main()
{
    vector<int> arr = { 2, 3, 7, 9, 5, 1, 6, 4, 3 };
    int k = 3;
 
    // Find the maximum element in each sliding window of
    // size k
    vector<int> result = maxSlidingWindow(arr, k);
 
    // Print the results
    for (auto i : result)
        cout << i << " ";
 
    return 0;
}

Java

import java.util.ArrayDeque;
import java.util.Deque;
 
public class MaxSlidingWindow {
    // Function to find the maximum element in each sliding
    // window of size k
    static int[] maxSlidingWindow(int[] arr, int k)
    {
        int n = arr.length;
        int[] ans = new int[n - k + 1];
        Deque<Integer> maxInWindow = new ArrayDeque<>();
 
        // Initialize maxInWindow with the first k elements
        for (int i = 0; i < k; i++) {
            while (!maxInWindow.isEmpty()
                   && arr[i]
                          >= arr[maxInWindow.peekLast()]) {
                maxInWindow.removeLast();
            }
            maxInWindow.addLast(i);
        }
 
        // The maximum element in the first window
        ans[0] = arr[maxInWindow.peekFirst()];
 
        // Process the remaining elements
        for (int i = k; i < n; i++) {
            // Remove elements that are out of the current
            // window
            while (!maxInWindow.isEmpty()
                   && maxInWindow.peekFirst() <= i - k) {
                maxInWindow.removeFirst();
            }
 
            // Remove elements that are not needed in the
            // current window
            while (!maxInWindow.isEmpty()
                   && arr[i]
                          >= arr[maxInWindow.peekLast()]) {
                maxInWindow.removeLast();
            }
 
            maxInWindow.addLast(i);
            ans[i - k + 1] = arr[maxInWindow.peekFirst()];
        }
 
        return ans;
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int[] arr = { 2, 3, 7, 9, 5, 1, 6, 4, 3 };
        int k = 3;
 
        // Find the maximum element in each sliding window
        // of size k
        int[] result = maxSlidingWindow(arr, k);
 
        // Print the results
        System.out.print(
            "Maximum elements in each sliding window: ");
        for (int i : result)
            System.out.print(i + " ");
    }
}

Python

from collections import deque
 
# Function to find the maximum element in each sliding window of size k
 
 
def maxSlidingWindow(arr, k):
    ans = []
    deq = deque()
 
    # Initialize the deque with the first k elements
    for i in range(k):
        while deq and arr[i] >= arr[deq[-1]]:
            deq.pop()
        deq.append(i)
 
    # The maximum element in the first window
    ans.append(arr[deq[0]])
 
    # Process the remaining elements
    for i in range(k, len(arr)):
        # Remove elements that are out of the current window
        while deq and deq[0] <= i - k:
            deq.popleft()
 
        # Remove elements that are less than the current element
        while deq and arr[i] >= arr[deq[-1]]:
            deq.pop()
 
        deq.append(i)
 
        # The maximum element in the current window
        ans.append(arr[deq[0]])
 
    return ans
 
 
# Main function
if __name__ == "__main__":
    arr = [2, 3, 7, 9, 5, 1, 6, 4, 3]
    k = 3
 
    # Find the maximum element in each sliding window of size k
    result = maxSlidingWindow(arr, k)
 
    # Print the results
    print(result)

C#

using System;
using System.Collections.Generic;
 
class Program {
    // Function to find the maximum element in each sliding
    // window of size k
    static List<int> MaxSlidingWindow(List<int> arr, int k)
    {
        List<int> ans = new List<int>();
        List<int> maxInWindow = new List<int>();
 
        // Initialize maxInWindow with the first k elements
        for (int i = 0; i < k; i++) {
            while (
                maxInWindow.Count > 0
                && arr[i]
                       >= arr[maxInWindow[maxInWindow.Count
                                          - 1]]) {
                maxInWindow.RemoveAt(maxInWindow.Count - 1);
            }
            maxInWindow.Add(i);
        }
 
        // The maximum element in the first window
        ans.Add(arr[maxInWindow[0]]);
 
        // Process the remaining elements
        for (int i = k; i < arr.Count; i++) {
            // Remove elements that are out of the current
            // window
            while (maxInWindow.Count > 0
                   && maxInWindow[0] <= i - k) {
                maxInWindow.RemoveAt(0);
            }
 
            // Remove elements that are not needed in the
            // current window
            while (
                maxInWindow.Count > 0
                && arr[i]
                       >= arr[maxInWindow[maxInWindow.Count
                                          - 1]]) {
                maxInWindow.RemoveAt(maxInWindow.Count - 1);
            }
 
            maxInWindow.Add(i);
            ans.Add(arr[maxInWindow[0]]);
        }
 
        return ans;
    }
 
    static void Main(string[] args)
    {
        List<int> arr
            = new List<int>{ 2, 3, 7, 9, 5, 1, 6, 4, 3 };
        int k = 3;
 
        List<int> result = MaxSlidingWindow(arr, k);
 
        Console.WriteLine(
            "Maximum elements in each sliding window:");
        foreach(int i in result) { Console.Write(i + " "); }
    }
}

Javascript

function maxSlidingWindow(arr, k) {
    const ans = [];
    const maxInWindow = [];
 
    // Initialize maxInWindow with the first k elements
    for (let i = 0; i < k; i++) {
        while (maxInWindow.length > 0 && arr[i] >= arr[maxInWindow[maxInWindow.length - 1]]) {
            maxInWindow.pop();
        }
        maxInWindow.push(i);
    }
 
    // The maximum element in the first window
    ans.push(arr[maxInWindow[0]]);
 
    // Process the remaining elements
    for (let i = k; i < arr.length; i++) {
        // Remove elements that are out of the current window
        while (maxInWindow.length > 0 && maxInWindow[0] <= i - k) {
            maxInWindow.shift();
        }
 
        // Remove elements that are not needed in the current window
        while (maxInWindow.length > 0 && arr[i] >= arr[maxInWindow[maxInWindow.length - 1]]) {
            maxInWindow.pop();
        }
 
        maxInWindow.push(i);
        ans.push(arr[maxInWindow[0]]);
    }
 
    return ans;
}
 
const arr = [2, 3, 7, 9, 5, 1, 6, 4, 3];
const k = 3;
 
const result = maxSlidingWindow(arr, k);
 
console.log("Maximum elements in each sliding window: " + result.join(' '));

Output

7 9 9 9 6 6 6

Time Complexity: O(NlogN), Where N is the size of the array.
Auxiliary Space: O(K), since size of set does not never exceeds K.

Sliding Window Maximum (Maximum of all subarrays of size K)

Given an array and an integer K, find the maximum for each and every contiguous subarray of size K.

Examples :

Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output: 3 3 4 5 5 5 6
Explanation: Maximum of 1, 2, 3 is 3
Maximum of 2, 3, 1 is 3
Maximum of 3, 1, 4 is 4
Maximum of 1, 4, 5 is 5
Maximum of 4, 5, 2 is 5
Maximum of 5, 2, 3 is 5
Maximum of 2, 3, 6 is 6

Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90
Explanation: Maximum of first 4 elements is 10, similarly for next 4
elements (i.e from index 1 to 4) is 10, So the sequence
generated is 10 10 10 15 15 90 90

Naive Approach:

The idea is very basic run a nested loop, the outer loop which will mark the starting point of the subarray of length K, the inner loop will run from the starting index to index+K, and print the maximum element among these K elements.

Follow the given steps to solve the problem:

Create a nested loop, the outer loop from starting index to N – Kth elements. The inner loop will run for K iterations.
Create a variable to store the maximum of K elements traversed by the inner loop.
Find the maximum of K elements traversed by the inner loop.
Print the maximum element in every iteration of the outer loop

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Method to find the maximum for each
// and every contiguous subarray of size K.
void printKMax(int arr[], int N, int K)
{
    int j, max;
 
    for (int i = 0; i <= N - K; i++) {
        max = arr[i];
 
        for (j = 1; j < K; j++) {
            if (arr[i + j] > max)
                max = arr[i + j];
        }
        cout << max << " ";
    }
}
 
// Driver's code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
   
      // Function call
    printKMax(arr, N, K);
    return 0;
}
 
// This code is contributed by rathbhupendra

C

// C program for the above approach
#include <stdio.h>
 
void printKMax(int arr[], int N, int K)
{
    int j, max;
 
    for (int i = 0; i <= N - K; i++) {
        max = arr[i];
 
        for (j = 1; j < K; j++) {
            if (arr[i + j] > max)
                max = arr[i + j];
        }
        printf("%d ", max);
    }
}
 
// Driver's Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
   
      // Function call
    printKMax(arr, N, K);
    return 0;
}

Java

// Java program for the above approach
 
public class GFG {
   
    // Method to find the maximum for
    // each and every contiguous
    // subarray of size K.
    static void printKMax(int arr[], int N, int K)
    {
        int j, max;
 
        for (int i = 0; i <= N - K; i++) {
 
            max = arr[i];
 
            for (j = 1; j < K; j++) {
                if (arr[i + j] > max)
                    max = arr[i + j];
            }
            System.out.print(max + " ");
        }
    }
 
    // Driver's code
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int K = 3;
       
          // Function call
        printKMax(arr, arr.length, K);
    }
}
 
// This code is contributed by Sumit Ghosh

C#

// C# program for the above approach
 
using System;
 
class GFG {
   
    // Method to find the maximum for
    // each and every contiguous subarray
    // of size k.
    static void printKMax(int[] arr, int N, int K)
    {
        int j, max;
 
        for (int i = 0; i <= N - K; i++) {
 
            max = arr[i];
 
            for (j = 1; j < K; j++) {
                if (arr[i + j] > max)
                    max = arr[i + j];
            }
            Console.Write(max + " ");
        }
    }
 
    // Driver's code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int K = 3;
        printKMax(arr, arr.Length, K);
    }
}
 
// This Code is Contributed by Sam007

Javascript

// JavaScript Program to find the maximum for 
// each and every contiguous subarray of size k.
 
// Method to find the maximum for each 
// and every contiguous subarray of size k.
function printKMax(arr,n,k) 
{ 
    let j, max; 
 
    for (let i = 0; i <= n - k; i++) 
    { 
        max = arr[i]; 
 
        for (j = 1; j < k; j++) 
        { 
            if (arr[i + j] > max) 
                max = arr[i + j]; 
        } 
         document.write( max + " "); 
    } 
} 
 
// Driver code
 
    let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; 
    let n =arr.length; 
    let k = 3; 
    printKMax(arr, n, k); 
 
// This code contributed by gauravrajput1 

PHP

<?php
// php program for the above approach
 
function printKMax($arr, $N, $K)
{
    $j; $max;
 
    for ($i = 0; $i <= $N - $K; $i++)
    {
        $max = $arr[$i];
 
        for ($j = 1; $j < $K; $j++)
        {
            if ($arr[$i + $j] > $max)
            $max = $arr[$i + $j];
        }
        printf("%d ", $max);
    }
}
 
// Driver's Code
$arr = array(1, 2, 3, 4, 5, 
             6, 7, 8, 9, 10);
$N = count($arr);
$K = 3;
 
// Function call
printKMax($arr, $N, $K);
 
// This Code is Contributed by anuj_67.
?>

Python3

# Python3 program for the above approach
 
# Method to find the maximum for each
# and every contiguous subarray
# of size K
 
def printMax(arr, N, K):
    max = 0
 
    for i in range(N - K + 1):
        max = arr[i]
        for j in range(1, K):
            if arr[i + j] > max:
                max = arr[i + j]
        print(str(max) + " ", end="")
 
 
# Driver's code
if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    N = len(arr)
    K = 3
     
    # Function call
    printMax(arr, N, K)
 
# This code is contributed by Shiv Shankar

Output

3 4 5 6 7 8 9 10

Time Complexity: O(N * K), The outer loop runs N-K+1 times and the inner loop runs K times for every iteration of the outer loop. So time complexity is O((n-k+1)*k) which can also be written as O(N * K)
Auxiliary Space: O(1)

Tags:

#Amazon #Directi #Flipkart #SAP Labs #sliding-window #Zoho #Arrays #DSA #Heap #Queue #Amazon #Directi #Flipkart #SAP Labs #Zoho #Arrays #Heap #Queue #sliding-window

Maximum of all subarrays of size K using Max-Heap:

Maximum of all subarrays of size K using Deque:

Maximum of all subarrays of size K using Set

C++

Java

Python

C#

Javascript

Sliding Window Maximum (Maximum of all subarrays of size K)

Naive Approach:

C++

C

Java

C#

Javascript

PHP

Python3

Similar Reads