Maximum of all subarrays of size K using Segment Tree

0 0 11 minutes read

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 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

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 log₂n.
- 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 *(2^ceil(log_²ⁿ⁾)-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 st
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] = 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 tree
node   -> 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 k
void 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 code
int 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 tree
import 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 st
static 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 tree
node   -> 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 k
static 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 code
public 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 tree
import 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 st
def 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] The
following parameters for
this function:
 
st     -> Pointer to segment tree
node -> 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 k
def 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 code
if __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 tree
using 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 st
static 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 tree
node   -> 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 k
static 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 code
public 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 tree
 
var 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 st
function 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 tree
node   -> 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 k
function 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 code
var k = 4;
var arr = [8, 5, 10, 7, 9, 4, 15,
              12, 90, 13];
var n = arr.length;
// Function to construct the
// segment tree
constructST(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 zambiatek!