Find maximum element from each sub-array of size 'k'| Set 1

Given input as an integer array and an integer 'k', find and print element with maximum value from each sub-array of size 'k'.
For example, for the input array {4,2,12,34,23,35,44,55} and for k = 3, output should be 12,34,34,35,44,55. Observe that 12 is the largest element in the first sub-array {4,2,12}, 34 is the largest element in the second and third sub-arrays - {2,12,34} and {12,34,23} and so on.


Video coming soon!



Subscribe for more updates


Algorithm/Insights

Simple approach: One of the intuitive ways to solve this problem could be to check all the sub-arrays of size 'k' and find out the maximum element from each of these sub-arrays. To check all the sub-arrays of size 'k', we start from a sub-array(window) of the first 'k' elements and then shift this window by one element until we reach the end of the array. There would be total 'n-k+1' such windows of 'k' elements each where 'n' denotes the size of the input array. In the following code snippet, this approach is implemented in function 'simplePrintMaxfromEachSubarray(int[] array, int k)'. Finding maximum element from sub-array of size 'k' takes O(k) time and there are total 'n-k+1' such sub-arrays. Therefore, overall time complexity of this approach is O(k(n-k+1)) which is equivalent to O(nk).

Optimized approach: In this approach, we make use of AVL trees (self-balanced Binary Search Tree) as explained in the  following algorithm. We will be referring to AVL tree as a BST in below steps because it would make understanding the intuition of the algorithm easier.
1. Create a BST from first 'k' elements of the input array.
2. Find node with maximum value from the BST created in step #1. Print this node's value. This would represent an element with maximum value from first sub-array of size 'k'.
3. Now starting from i = 0 upto i = n-k-1
    a. Search and delete element with value array[i] from the BST.
    b. Insert node with value as array[i+k] into the BST. Now this BST represents next sub-array of size 'k'.
    c. Find node with maximum value from the BST. Print this node's value.

Handling duplicates: Note that this optimized approach which uses BST won't be able to handle the case when input array has more than one elements with same value. We can handle this case easily by pre-processing the input array such that whenever there are duplicates, their values are modified by adding different decimal offsets. For example, if the given input array is {2,3,6,5,6,5} then it could be modified to {2,3,6.01,5.01,6.02,5.02}. Now this modified input does not have any duplicates and above algorithm should work. Care has to taken to remove the decimal part while printing the value of maximum element in a sub-array.

In the above algorithm, creating BST takes O(logk) time. Search and delete operation, insert operation and finding maximum valued node operation, each of these operations takes O(logk) time and we need to perform each of these operations 'n-k' times. Therefore, overall time complexity of this algorithm is O(nlogk). Extra space taken in the form of BST is O(k).
You can check out function 'printMaxfromEachSubarray(int[] array, int k)' in the following code snippet for implementation details.

Please feel free to add any queries/comments you might have in the below section.


Algorithm Visualization




Code Snippet

			
package com.ideserve.nilesh.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a> 
 * In O(nlogk) time, this code finds out maximum element from each sub-array of size 'k'.
 * @author Nilesh
 */
public class MaximumfromEachSubarray 
{
    private class AVLTreeNode 
    {
        int data;
        AVLTreeNode left;
        AVLTreeNode right;
        int height;
        
        AVLTreeNode(int data)
        {
            this.data = data;
            this.height = 1;
        }
    }
    
    AVLTreeNode root;
    
    public MaximumfromEachSubarray()
    {

    }
    
    private int getHeight(AVLTreeNode node)
    {
        if (node == null)
            return 0;
        
        return node.height;
    }
    
    private void updateHeight(AVLTreeNode node)
    {
        if (node == null) return;
        
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
    }
    
    
    private AVLTreeNode rotateRight(AVLTreeNode node)
    {
        if (node == null) return node;
        
        AVLTreeNode beta  = node.left;
        
        AVLTreeNode t2  = beta.right;
        
        beta.right = node;
        node.left = t2;
        
        // we first need to update the height of node because height of beta uses height of node
        updateHeight(node);
        
        // now we update height of beta
        updateHeight(beta);
        
        return beta;
    }
    
    
    private AVLTreeNode rotateLeft(AVLTreeNode node)
    {
        if (node == null) return node;
        
        AVLTreeNode beta  = node.right;
        AVLTreeNode t2  = beta.left;
        
        beta.left = node;
        node.right = t2;
        
        // we first need to update the height of node because height of beta uses height of node
        updateHeight(node);
        
        // now we update height of beta
        updateHeight(beta);
        
        return beta;
    }
    
    
    private int getBalance(AVLTreeNode node)
    {
        if (node == null)
        {
            return 0;
        }
        int balance;
        
        balance = getHeight(node.left) - getHeight(node.right);
        
        return balance;
    }
    
    
    private int getMaxValue(AVLTreeNode node)
    {
        // though this case should not be hit ever for the usecase this function is employed for
        if (node == null) return Integer.MIN_VALUE;
        
        // if this is the left-most node
        if (node.right == null) return node.data;
        
        return getMaxValue(node.right);
    }
    
    private int getMinValue(AVLTreeNode node)
    {
        // though this case should not be hit ever for the usecase this function is employed for
        if (node == null) return Integer.MIN_VALUE;
        
        // if this is the left-most node
        if (node.right == null) return node.data;
        
        return getMaxValue(node.left);
    }
    
    private AVLTreeNode delete(AVLTreeNode node, int key)
    {
        // if empty tree 
        if (node == null) return null;
        
        if (key < node.data)
        {
            node.left = delete(node.left, key);
        }
        else if (key > node.data)
        {
            node.right = delete(node.right, key);
        }
        
        else // key to be deleted is equal to node data 
        {
            // one child/no child case
            if (node.left == null)
            {
                node = node.right;
            }
            else if (node.right == null)
            {
                node = node.left;
            }
            
            // two children case
            // copy value of inorder successor into current node and delete inorder successor
            // since right sub-tree would be modified, update node.right
            else
            {
                int inorderSuccessorValue = getMinValue(node.right);
                node.data = inorderSuccessorValue;
                node.right = delete(node.right, inorderSuccessorValue);
            }
        }

        // if there was only one node in the tree which got deleted above return null 
        if (node == null)
        {
            return null;
        }
        
        // update the height of the node
        updateHeight(node);
        
        // check the balance at this node and perform rotations accordingly
        int balance = getBalance(node);
        
        if (balance > 1) // indicates either left-left or left-right case
        {
            if (getBalance(node.left) >= 0) // confirms left-left case
            {
                node = rotateRight(node);
            }
            else // confirms left-right case
            {
                node.left = rotateLeft(node.left);
                node = rotateRight(node);
            }
        }
        
        else if (balance < -1) // indicates either right-right or right-left case
        {
            if (getBalance(node.right) <= 0) // confirms right-right case
            {
                node = rotateLeft(node);
            }
            else // confirms right-left case
            {
                node.right = rotateRight(node.right);
                node = rotateLeft(node);
            }
        }
        return node;
    }
    
    
    private AVLTreeNode insert(AVLTreeNode node, int key)
    {
        // do usual BST insertion first
        if (node == null)
        {
            this.root =  new AVLTreeNode(key);
            return this.root;
        }
        
        if (key < node.data)
        {
            node.left = insert(node.left, key);
        }
        else if (key > node.data)
        {
            node.right = insert(node.right, key);
        }
        else
        {
            return node;
        }
        
        // now update the height of the node
        updateHeight(node);
        
        // check the balance at this node and perform rotations accordingly
        int balance = getBalance(node);
        
        if (balance > 1) // indicates either left-left or left-right case
        {
            if (key < node.left.data) // confirms left-left case
            {
                node = rotateRight(node);
            }
            else // confirms left-right case
            {
                node.left = rotateLeft(node.left);
                node = rotateRight(node);
            }
        }
        
        else if (balance < -1) // indicates either right-right or right-left case
        {
            if (key > node.right.data) // confirms right-right case
            {
                node = rotateLeft(node);
            }
            else // confirms right-left case
            {
                node.right = rotateRight(node.right);
                node = rotateLeft(node);
            }
        }
        return node;
    }
    
    
    public void insert(int key)
    {
        root = insert(this.root, key);
        return;
    }
    
    
    public void delete(int key)
    {
        root = delete(this.root, key);
        return;
    }
    

    private void printMax(int[] array, int low, int high)
    {
        int maxValue = Integer.MIN_VALUE;
        for (int i = low; i <= high; i++)
        {
            if (array[i] > maxValue)
            {
                maxValue = array[i];
            }
        }
        
        System.out.println(maxValue);
    }
    
    public void simplePrintMaxfromEachSubarray(int[] array, int k)
    {
        // {4,2,12,34,23,35,44,55};
        
        int low = 0, high = low + k - 1;
        
        while (high < array.length)
        {
            printMax(array, low, high);
            low  += 1;
            high += 1;
        }
    }
    
    public void printMaxfromEachSubarray(int[] array, int k)
    {
        // create a balanced BST by inserting first 'k' keys 
        for (int i = 0; i < k; i++)
        {
            insert(array[i]);
        }
        // print the maximum value of first sub-array of 'k' elements
        System.out.println(getMaxValue(root));
        
        /*
         *  Now find maximum element for each remaining contiguous sub-array of size 'k'
         *  1. delete 'i'th element from BST
         *  2. insert (i+k)th element into BST
         *  3. find element with maximum value in this modified BST
         */
        for (int i = 0; i < array.length-k; i++)
        {
            delete(array[i]); 
            insert(array[i+k]);
            System.out.println(getMaxValue(root));
        }
    }

    public static void main(String[] args)
    {
        MaximumfromEachSubarray solution = new MaximumfromEachSubarray();

        int[] array = {4,2,12,34,23,35,44,55};
        int k = 3;
        
        System.out.println("Maximum elements from each sub-array of specified size are - ");
        solution.printMaxfromEachSubarray(array, k);
    }
}
		

Order of the Algorithm

Time Complexity is O(nlogk), n: size of input array, k: sub-array size
Space Complexity is O(k)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer