Given an array arr[] and an integer K, the task is to 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 6Input: 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
Approach:
The idea is to use the Segment tree to answer the maximum of all subarrays of size K.
- Representation of Segment trees
- Leaf Nodes are the elements of the input array.
- Each internal node represents the maximum of all of its children.
- Construction of Segment Tree from the given array:
- We start with a segment arr[0 . . . n-1], and every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the maximum value in a segment tree node.
- All levels of the constructed segment tree will be completely filled except the last level. Also, the tree will be a full Binary Tree because we always divide segments into two halves at every level.
- Since the constructed tree is always a full binary tree with n leaves, there will be n – 1 internal nodes. So total nodes will be 2 * n – 1.
- The height of the segment tree will be log2n.
- Since the tree is represented using an array and the relation between parent and child indexes must be maintained, the size of memory allocated for the segment tree will be 2 *(2ceil(log2n))-1.
Below is the implementation of the above approach.
C++
// C++ program to answer Maximum// of allsubarrays of size k// using segment tree#include <bits/stdc++.h>using namespace std;#define MAX 1000000// Size of segment// tree = 2^{log(MAX)+1}int st[3 * MAX];// A utility function to get the// middle index of given range.int getMid(int s, int e){ return s + (e - s) / 2;}// A recursive function that// constructs Segment Tree for// array[s...e]. node is index// of current node in segment// tree stvoid constructST(int node, int s, int e, int arr[]){ // If there is one element in // array, store it in current // node of segment tree and return if (s == e) { st[node] = arr[s]; return; } // If there are more than // one elements, then recur // for left and right subtrees // and store the max of // values in this node int mid = getMid(s, e); constructST(2 * node, s, mid, arr); constructST(2 * node + 1, mid + 1, e, arr); st[node] = max(st[2 * node], st[2 * node + 1]);}/* A recursive function to get the maximum of range[l, r] The following parameters for this function:st -> Pointer to segment treenode -> Index of current node in the segment tree .s & e -> Starting and ending indexes of the segment represented by current node, i.e., st[node]l & r -> Starting and ending indexes of range query */int getMax(int node, int s, int e, int l, int r){ // If segment of this node // does not belong to // given range if (s > r || e < l) return INT_MIN; // If segment of this node // is completely part of // given range, then return // the max of segment if (s >= l && e <= r) return st[node]; // If segment of this node // is partially the part // of given range int mid = getMid(s, e); return max(getMax(2 * node, s, mid, l, r), getMax(2 * node + 1, mid + 1, e, l, r));}// Function to print the max// of all subarrays of size kvoid printKMax(int n, int k){ for (int i = 0; i < n; i++) { if ((k - 1 + i) < n) cout << getMax(1, 0, n - 1, i, k - 1 + i) << " "; else break; }}// Driver codeint main(){ int k = 4; int arr[] = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 }; int n = sizeof(arr) / sizeof(arr[0]); // Function to construct the // segment tree constructST(1, 0, n - 1, arr); printKMax(n, k); return 0;} |
Java
// Java program to answer Maximum// of allsubarrays of size k// using segment treeimport java.io.*;import java.util.*;class GFG{static int MAX = 1000000;// Size of segment// tree = 2^{log(MAX)+1}static int[] st = new int[3 * MAX];// A utility function to get the// middle index of given range.static int getMid(int s, int e){ return s + (e - s) / 2;}// A recursive function that// constructs Segment Tree for// array[s...e]. node is index// of current node in segment// tree ststatic void constructST(int node, int s, int e, int[] arr){ // If there is one element in // array, store it in current // node of segment tree and return if (s == e) { st[node] = arr[s]; return; } // If there are more than // one elements, then recur // for left and right subtrees // and store the max of // values in this node int mid = getMid(s, e); constructST(2 * node, s, mid, arr); constructST(2 * node + 1, mid + 1, e, arr); st[node] = Math.max(st[2 * node], st[2 * node + 1]);}/* A recursive function to get the maximum of range[l, r] The following parameters for this function:st -> Pointer to segment treenode -> Index of current node in the segment tree .s & e -> Starting and ending indexes of the segment represented by current node, i.e., st[node]l & r -> Starting and ending indexes of range query */static int getMax(int node, int s, int e, int l, int r){ // If segment of this node // does not belong to // given range if (s > r || e < l) return Integer.MIN_VALUE; // If segment of this node // is completely part of // given range, then return // the max of segment if (s >= l && e <= r) return st[node]; // If segment of this node // is partially the part // of given range int mid = getMid(s, e); return Math.max(getMax(2 * node, s, mid, l, r), getMax(2 * node + 1, mid + 1, e, l, r));}// Function to print the max// of all subarrays of size kstatic void printKMax(int n, int k){ for(int i = 0; i < n; i++) { if ((k - 1 + i) < n) System.out.print(getMax(1, 0, n - 1, i, k - 1 + i) + " "); else break; }}// Driver codepublic static void main(String[] args){ int k = 4; int[] arr = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 }; int n = arr.length; // Function to construct the // segment tree constructST(1, 0, n - 1, arr); printKMax(n, k);}}// This code is contributed by akhilsaini |
Python3
# Python3 program to answer maximum# of all subarrays of size k# using segment treeimport sys MAX = 1000000# Size of segment# tree = 2^{log(MAX)+1}st = [0] * (3 * MAX)# A utility function to get the# middle index of given range.def getMid(s, e): return s + (e - s) // 2 # A recursive function that# constructs Segment Tree for# array[s...e]. node is index# of current node in segment# tree stdef constructST(node, s, e, arr): # If there is one element in # array, store it in current # node of segment tree and return if (s == e): st[node] = arr[s] return # If there are more than # one elements, then recur # for left and right subtrees # and store the max of # values in this node mid = getMid(s, e) constructST(2 * node, s, mid, arr) constructST(2 * node + 1, mid + 1, e, arr) st[node] = max(st[2 * node], st[2 * node + 1])''' A recursive function to get the maximum of range[l, r] Thefollowing parameters forthis function:st -> Pointer to segment treenode -> Index of current node in the segment tree .s & e -> Starting and ending indexes of the segment represented by current node, i.e., st[node]l & r -> Starting and ending indexes of range query'''def getMax(node, s, e, l, r): # If segment of this node # does not belong to # given range if (s > r or e < l): return (-sys.maxsize - 1) # If segment of this node # is completely part of # given range, then return # the max of segment if (s >= l and e <= r): return st[node] # If segment of this node # is partially the part # of given range mid = getMid(s, e) return max(getMax(2 * node, s, mid, l, r), getMax(2 * node + 1, mid + 1, e, l, r))# Function to print the max# of all subarrays of size kdef printKMax(n, k): for i in range(n): if ((k - 1 + i) < n): print(getMax(1, 0, n - 1, i, k - 1 + i), end = " ") else: break# Driver codeif __name__ == "__main__": k = 4 arr = [ 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 ] n = len(arr) # Function to construct the # segment tree constructST(1, 0, n - 1, arr) printKMax(n, k)# This code is contributed by chitranayal |
C#
// C# program to answer Maximum// of allsubarrays of size k// using segment treeusing System;class GFG{static int MAX = 1000000;// Size of segment// tree = 2^{log(MAX)+1}static int[] st = new int[3 * MAX];// A utility function to get the// middle index of given range.static int getMid(int s, int e) { return s + (e - s) / 2; }// A recursive function that// constructs Segment Tree for// array[s...e]. node is index// of current node in segment// tree ststatic void constructST(int node, int s, int e, int[] arr){ // If there is one element in // array, store it in current // node of segment tree and return if (s == e) { st[node] = arr[s]; return; } // If there are more than // one elements, then recur // for left and right subtrees // and store the max of // values in this node int mid = getMid(s, e); constructST(2 * node, s, mid, arr); constructST(2 * node + 1, mid + 1, e, arr); st[node] = Math.Max(st[2 * node], st[2 * node + 1]);}/* A recursive function to get the maximum of range[l, r] The following parameters for this function:st -> Pointer to segment treenode -> Index of current node in the segment tree .s & e -> Starting and ending indexes of the segment represented by current node, i.e., st[node]l & r -> Starting and ending indexes of range query */static int getMax(int node, int s, int e, int l, int r){ // If segment of this node // does not belong to // given range if (s > r || e < l) return int.MinValue; // If segment of this node // is completely part of // given range, then return // the max of segment if (s >= l && e <= r) return st[node]; // If segment of this node // is partially the part // of given range int mid = getMid(s, e); return Math.Max(getMax(2 * node, s, mid, l, r), getMax(2 * node + 1, mid + 1, e, l, r));}// Function to print the max// of all subarrays of size kstatic void printKMax(int n, int k){ for(int i = 0; i < n; i++) { if ((k - 1 + i) < n) Console.Write(getMax(1, 0, n - 1, i, k - 1 + i) + " "); else break; }}// Driver codepublic static void Main(){ int k = 4; int[] arr = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 }; int n = arr.Length; // Function to construct the // segment tree constructST(1, 0, n - 1, arr); printKMax(n, k);}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program to answer Maximum// of allsubarrays of size k// using segment treevar MAX = 1000000;// Size of segment// tree = 2^{log(MAX)+1}var st = Array(3*MAX);// A utility function to get the// middle index of given range.function getMid(s, e){ return s + parseInt((e - s) / 2);}// A recursive function that// constructs Segment Tree for// array[s...e]. node is index// of current node in segment// tree stfunction constructST(node, s, e, arr){ // If there is one element in // array, store it in current // node of segment tree and return if (s == e) { st[node] = arr[s]; return; } // If there are more than // one elements, then recur // for left and right subtrees // and store the max of // values in this node var mid = getMid(s, e); constructST(2 * node, s, mid, arr); constructST(2 * node + 1, mid + 1, e, arr); st[node] = Math.max(st[2 * node], st[2 * node + 1]);}/* A recursive function to get the maximum of range[l, r] The following parameters for this function:st -> Pointer to segment treenode -> Index of current node in the segment tree .s & e -> Starting and ending indexes of the segment represented by current node, i.e., st[node]l & r -> Starting and ending indexes of range query */function getMax(node, s, e, l, r){ // If segment of this node // does not belong to // given range if (s > r || e < l) return -1000000000; // If segment of this node // is completely part of // given range, then return // the max of segment if (s >= l && e <= r) return st[node]; // If segment of this node // is partially the part // of given range var mid = getMid(s, e); return Math.max(getMax(2 * node, s, mid, l, r), getMax(2 * node + 1, mid + 1, e, l, r));}// Function to print the max// of all subarrays of size kfunction printKMax(n, k){ for (var i = 0; i < n; i++) { if ((k - 1 + i) < n) document.write( getMax(1, 0, n - 1, i, k - 1 + i) + " "); else break; }}// Driver codevar k = 4;var arr = [8, 5, 10, 7, 9, 4, 15, 12, 90, 13];var n = arr.length;// Function to construct the// segment treeconstructST(1, 0, n - 1, arr);printKMax(n, k);</script> |
Output:
10 10 10 15 15 90 90
Time Complexity: O(N * log K)
Auxiliary Space: O(N * log K)
Related Article: Sliding Window Maximum (Maximum of all subarrays of size k)
Related Topic: Segment Tree
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
