Given an array arr[] of length N, two arrays start[] and end[] of size M each where {start[i], end[i]} denotes a subarray of arr[] and an integer base, the task is to determine the maximum height of a tower with given base that can be formed using elements from a single subarray bounded by any {start[i], end[i]} and satisfying the following conditions:
- All elements in each level should be equal.
- Number of elements in each level is the same as base.
- No two level can have the same element.
Example to understand the problem
Examples:
Input: N = 9, arr[] = {1, 5, 7, 3, 2, 4, 6, 9, 8}, M = 3, start[] = {0, 3, 5}, end[] = {8, 5, 6}, base = 1
Output: 9
Explanation:
First Subarray = {0, 8}. There are 9 different elements.
Each element can be kept at a different level.
So the height of the tower can be maximum 9 as base is 1.
Second Subarray = {3, 5}. There are 3 unique elements.
So it will have height 3 at maximum.
Third Subarray = {5, 6}. We can form a tower of max height 2.
The maximum height among all the sub-arrays = 9.Input: N = 5, arr[] = {1, 3, 3, 7, 5}, M = 2, start[] = {0, 1}, end[] = {0, 3}, base = 2
Output: 1
Explanation:
First Subarray = {0, 0}. height = 0 for this sub-array,
because no tower of base 2 can be formed.
Second Sub-array = {1, 2}. Tower of height 1 can be formed by using
arr[1] and arr[2] at 1st level of tower.
The maximum height of the tower that can be obtained from all the above subarrays is 1.
Approach: To solve the problem follow the below idea:
Count the frequency of each distinct element for each sub-array using Hash-Map. Initialized current_height a variable to zero, Traverse on Hash-Map and if an element’s frequency is greater than or equal to base then increment the current_height. Print the maximum value of Height H among all the sub-arrays.
Follow the steps to solve the problem:
- Create a max_height variable and set it as max_height = 0. Then for each sub-array follow these sub-steps:
- Create a Hash-Map and a current_variable = 0.
- Count the frequency of each distinct element and store it in Hash-Map as pair of <element, frequency>.
- While traversing on Hash-Map, if the frequency of a pair in Hash-Map is greater than or equal to the base of Tower, then increment current_height, and if current_height is greater than max_height then update max_height as current_height.
- Print the value of the max_height variable.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to obtain Maximum// height of towerint Max_height(int n, int arr[], int m, int start[], int end[], int base){ // Variable to store Maximum height // of tower among all sub-array int max_height = 0; // Loop for obtaining maximum value // of H for all sub-arrays for (int i = 0; i < m; i++) { // Variable to current height // for each sub-array int current_height = 0; // Variable to store start // point of each sub-array int start_point = start[i]; // Variable to store start // point of each sub-array int end_point = end[i]; // HashMap initialized to // store frequencies unordered_map<int, int> map; // Loop for Traversing // on sub-array for (int j = start_point; j <= end_point; j++) { // Updating frequencies in // Hash-Map for each // distinct element present // in sub-array map[arr[j]]++; } // For loop for traversing // on Map for (auto it = map.begin(); it != map.end(); it++) { if (it->second >= base) { // Updating value of // current_height current_height++; // Updating value of // max_height by // comparing it with // current_height max_height = current_height > max_height ? current_height : max_height; } } } // Printing value of max height // among all subarrays return max_height;}// Driver Functionint main(){ int N = 9; int arr[] = {1, 5, 7, 3, 2, 4, 6, 9, 8}; int M = 3; int start[] = {0, 3, 5}; int end[] = {8, 5, 6}; int base = 1; // Function call cout << (Max_height(N, arr, M, start, end, base));}// This code is contributed by Potta Lokesh |
Java
// Java code to implement the approachimport java.util.*;class GFG { // Driver Function public static void main(String[] args) { int N = 9; int arr[] = { 1, 5, 7, 3, 2, 4, 6, 9, 8 }; int M = 3; int start[] = { 0, 3, 5 }; int end[] = { 8, 5, 6 }; int base = 1; // Function call System.out.println( Max_height(N, arr, M, start, end, base)); } // Function to obtain Maximum // height of tower static int Max_height(int n, int[] arr, int m, int[] start, int[] end, int base) { // Variable to store Maximum height // of tower among all sub-array int max_height = 0; // Loop for obtaining maximum value // of H for all sub-arrays for (int i = 0; i < m; i++) { // Variable to current height // for each sub-array int current_height = 0; // Variable to store start // point of each sub-array int start_point = start[i]; // Variable to store start // point of each sub-array int end_point = end[i]; // HashMap initialized to // store frequencies HashMap<Integer, Integer> map = new HashMap<>(); // Loop for Traversing // on sub-array for (int j = start_point; j <= end_point; j++) { // Updating frequencies in // Hash-Map for each // distinct element present // in sub-array map.put(arr[j], map.get(arr[j]) == null ? 1 : map.get(arr[j]) + 1); } // For loop for traversing // on Map for (Map.Entry<Integer, Integer> set : map.entrySet()) { if (set.getValue() >= base) { // Updating value of // current_height current_height++; // Updating value of // max_height by // comparing it with // current_height max_height = current_height > max_height ? current_height : max_height; } } } // Printing value of max height // among all subarrays return max_height; }} |
Python3
# Python code to implement the approach# Function to obtain Maximum# height of towerdef Max_height(n, arr, m, start, end, base): # Variable to store Maximum height # of tower among all sub-array max_height = 0 # Loop for obtaining maximum value # of H for all sub-arrays for i in range(m): # Variable to current height # for each sub-array current_height = 0 # Variable to store start # point of each sub-array start_point = start[i] # Variable to store start # point of each sub-array end_point = end[i] # HashMap initialized to # store frequencies mp = {} # Loop for Traversing # on sub-array for j in range(start_point, end_point+1): # Updating frequencies in # Hash-Map for each # distinct element present # in sub-array if mp.get(arr[j]) == None: mp[arr[j]] = 1 else: mp[arr[j]] += 1 # For loop for traversing # on Map for first, second in mp.items(): if (second >= base): # Updating value of # current_height current_height += 1 # Updating value of # max_height by # comparing it with # current_height max_height = current_height if ( current_height > max_height) else max_height # Printing value of max height # among all subarrays return max_height# Driver Functionif __name__ == "__main__": N = 9 arr = [1, 5, 7, 3, 2, 4, 6, 9, 8] M = 3 start = [0, 3, 5] end = [8, 5, 6] base = 1 # Function call print(Max_height(N, arr, M, start, end, base))# This code is contributed by Rohit Pradhan |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { static public void Main() { // Code int N = 9; int[] arr = { 1, 5, 7, 3, 2, 4, 6, 9, 8 }; int M = 3; int[] start = { 0, 3, 5 }; int[] end = { 8, 5, 6 }; int Base = 1; // Function call Console.WriteLine( Max_height(N, arr, M, start, end, Base)); } // Function to obtain Maximum // height of tower static int Max_height(int n, int[] arr, int m, int[] start, int[] end, int Base) { // Variable to store Maximum height // of tower among all sub-array int max_height = 0; // Loop for obtaining maximum value // of H for all sub-arrays for (int i = 0; i < m; i++) { // Variable to current height // for each sub-array int current_height = 0; // Variable to store start // point of each sub-array int start_point = start[i]; // Variable to store start // point of each sub-array int end_point = end[i]; // HashMap initialized to // store frequencies Dictionary<int, int> map = new Dictionary<int, int>(); // Loop for Traversing // on sub-array for (int j = start_point; j <= end_point; j++) { // Updating frequencies in // Hash-Map for each // distinct element present // in sub-array if (map.ContainsKey(arr[j])) { map[arr[j]] += 1; } else { map[arr[j]] = 1; } } // For loop for traversing // on Map foreach(KeyValuePair<int, int> Set in map) { if (Set.Value >= Base) { //Updating value of // current_height current_height++; // Updating value of // max_height by // comparing it with // current_height max_height = current_height > max_height ? current_height : max_height; } } } // Printing value of max height // among all subarrays return max_height; }}// This code is contributed by lokeshmvs21. |
Javascript
<script>// Function to obtain Maximum// height of towerfunction Max_height( n, arr, m, start, end, base){ // Variable to store Maximum height // of tower among all sub-array let max_height = 0; // Loop for obtaining maximum value // of H for all sub-arrays for (let i = 0; i < m; i++) { // Variable to current height // for each sub-array let current_height = 0; // Variable to store start // point of each sub-array let start_point = start[i]; // Variable to store start // point of each sub-array let end_point = end[i]; // HashMap initialized to // store frequencies // unordered_map<int, int> map; let map = {}; // Loop for Traversing // on sub-array for (let j = start_point; j <= end_point; j++) { // Updating frequencies in // Hash-Map for each // distinct element present // in sub-array if(map[arr[j]]==NaN || map[arr[j]]==undefined)map[arr[j]]=0; map[arr[j]]++; } // For loop for traversing // on Map let count = 0; for (var c in map) { count = count + 1; } for (let it = start_point; it <=count ; it++) { if (map[it] >= base) { // Updating value of // current_height current_height++; // Updating value of // max_height by // comparing it with // current_height max_height = current_height > max_height ? current_height : max_height; } } } // Printing value of max height // among all subarrays return max_height;}let N = 9;let arr = [1, 5, 7, 3, 2, 4, 6, 9, 8];let M = 3;let start = [0, 3, 5];let end = [8, 5, 6];let base = 1;// Function callconsole.log(Max_height(N, arr, M, start, end, base));// This code is contributed by akashish__</script> |
Output
9
Time Complexity: O(M*N)
Auxiliary Space: O(N)
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!
