Given two arrays arr[] and q[] consisting of N integers, the task is for each query q[i] is to determine the number of times the maximum array element occurs in the subarray [q[i], arr[N – 1]].
Examples:
Input: arr[] = {5, 4, 5, 3, 2}, q[] = {1, 2, 3, 4, 5}
Output: 2 1 1 1 1
Explanation:
For the first query index start from 1. The subarray is [5, 4, 5, 3, 2], the maximum value is 5 and it’s occurrence in subarray is 2.
For the second query index start from 2. The subarray is [4, 5, 3, 2], the maximum value is 5 and it’s occurrence in subarray is 1.
For the third query index start from 3. The subarray is [5, 3, 2], the maximum value is 5 and it’s occurrence in subarray is 1.
For the forth query index start from 4. The subarray is [3, 2], the maximum value is 3 and it’s occurrence in subarray is 1.
For the fifth query index start from 5. The subarray is [2], the maximum value is 2 and it’s occurrence in subarray is 1.Input: arr[] = {2, 1, 2}, q[] = {1, 2, 3}
Output: 2 1 1
Naive Approach: The simplest approach is to traverse the array and find the maximum array element. Now, for each query q[i], traverse the subarray [q[i], arr[N – 1]], and print the count of occurrences of the maximum element in the subarray.
Follow the steps below to implement the above idea:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find occurrence of// max element in given subarrayvoid FreqOfMaxElement(vector<int> arr, vector<int> q){ // Traverse over each query for (int i = 0; i < q.size(); i++) { // Find the starting index of each query int start = q[i] - 1; int count = 0; // Find the maximum element in the range of each // query int maxx = *max_element(arr.begin() + start, arr.end()); // Find the occurrences of maxx element for (int j = start; j < arr.size(); j++) { if (arr[j] == maxx) { count++; } } // Print the count cout << count << " "; }}// Driver Codeint main(){ vector<int> arr = { 5, 4, 5, 3, 2 }; vector<int> q = { 1, 2, 3, 4, 5 }; // Function Call FreqOfMaxElement(arr, q);} |
Java
import java.util.*;import java.io.*;public class Gfg { // Function to find occurrence of // max element in given subarray public static void FreqOfMaxElement(List<Integer> arr, List<Integer> q) { // Traverse over each query for (int i = 0; i < q.size(); i++) { // Find the starting index of each query int start = q.get(i) - 1; int count = 0; // Find the maximum element in the range of each // query int maxx = Collections.max(arr.subList(start, arr.size())); // Find the occurrences of maxx element for (int j = start; j < arr.size(); j++) { if (arr.get(j) == maxx) { count++; } } // Print the count System.out.print(count + " "); } } // Driver Code public static void main(String[] args) { List<Integer> arr = Arrays.asList(5, 4, 5, 3, 2); List<Integer> q = Arrays.asList(1, 2, 3, 4, 5); // Function Call FreqOfMaxElement(arr, q); }} |
Python3
from collections import Counter def FreqOfMaxElement(arr, q): # Traverse over each query for i in range(len(q)): # Find the starting index of each query start = q[i] - 1 count = 0 # Find the maximum element in the range of each query maxx = max(arr[start:]) # Find the occurrences of maxx element for j in range(start, len(arr)): if arr[j] == maxx: count += 1 # Print the count print(count, end = " ") # Driver Code if __name__ == "__main__": arr = [5, 4, 5, 3, 2] q = [1, 2, 3, 4, 5] FreqOfMaxElement(arr, q) # This code is contributed by aadityaburujwale. |
C#
// C# program for the above approachusing System;using System.Linq;using System.Collections.Generic;class GFG { // Function to find occurrence of // max element in given subarray static void FreqOfMaxElement(int[] arr,int[] q) { // Traverse over each query for (int i = 0; i < q.Length; i++) { // Find the starting index of each query int start = q[i] - 1; int count = 0; // Find the maximum element in the range of each // query int maxx=-1; for(int j=start; j<arr.Length; j++) maxx=Math.Max(maxx, arr[j]); // Find the occurrences of maxx element for (int j = start; j < arr.Length; j++) { if (arr[j] == maxx) { count++; } } // Print the count Console.Write(count + " "); } } // Driver Code public static void Main (string[] args) { int[] arr = { 5, 4, 5, 3, 2 }; int[] q = { 1, 2, 3, 4, 5 }; // Function Call FreqOfMaxElement(arr, q); }} |
Javascript
// Javascript program for the above approach// Function to find occurrence of// max element in given subarrayfunction FreqOfMaxElement(arr, q){ // Traverse over each query for (let i = 0; i < q.length; i++) { // Find the starting index of each query let start = q[i] - 1; let count = 0; // Find the maximum element in the range of each // query let maxx=Number.MIN_SAFE_INTEGER; for(let i=start; i<arr.length; i++) { maxx=Math.max(arr[i], maxx); } // Find the occurrences of maxx element for (let j = start; j < arr.length; j++) { if (arr[j] == maxx) { count++; } } // Print the count document.write(count); document.write(" "); }}// Driver Codelet arr = [ 5, 4, 5, 3, 2 ];let q = [ 1, 2, 3, 4, 5 ];// Function CallFreqOfMaxElement(arr, q); |
Output
2 1 1 1 1
Time Complexity: O(N*Q), where N and Q are the lengths of the given array and query respectively.
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Hashing. Below are the steps:
- Create an array maxFreqVec[] to store the occurrence of the max element from given index q[i] to N.
- Traverse the array arr[] from the right and keep track of the maximum element in the array and update the array maxFreqVec[] at that index with the occurrence of that maximum element.
- After the above steps, traverse over the array q[] and print the value maxFreqVec[q[i] – 1] as the maximum element in each subarray for each query.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include<bits/stdc++.h>using namespace std;// Function to find occurrence of// max element in given subarrayvoid FreqOfMaxElement(vector<int> arr, vector<int> q){ // Store the frequency of maximum // element vector<int> maxFreqVec(arr.size()); int maxSoFar = INT_MIN; int maxFreq = 0; // Traverse over the array arr[] // from right to left for(int i = arr.size() - 1; i >= 0; i--) { // If curr element is greater // than maxSofar if (arr[i] > maxSoFar) { // Reset maxSofar and maxFreq maxSoFar = arr[i]; maxFreq = 1; } // If curr is equal to maxSofar else if (arr[i] == maxSoFar) { // Increment the maxFreq maxFreq++; } // Update maxFreqVec[i] maxFreqVec[i] = maxFreq; } // Print occurrence of maximum // element for each query for(int k : q) { cout << maxFreqVec[k - 1] << " "; }}// Driver Codeint main(){ vector<int> arr = { 5, 4, 5, 3, 2 }; vector<int> q = { 1, 2, 3, 4, 5 }; // Function Call FreqOfMaxElement(arr, q);}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG { // Function to find occurrence of // max element in given subarray static void FreqOfMaxElement( int[] arr, int[] q) { // Store the frequency of maximum // element int[] maxFreqVec = new int[arr.length]; int maxSoFar = Integer.MIN_VALUE; int maxFreq = 0; // Traverse over the array arr[] // from right to left for (int i = arr.length - 1; i >= 0; i--) { // If curr element is greater // than maxSofar if (arr[i] > maxSoFar) { // Reset maxSofar and maxFreq maxSoFar = arr[i]; maxFreq = 1; } // If curr is equal to maxSofar else if (arr[i] == maxSoFar) { // Increment the maxFreq maxFreq++; } // Update maxFreqVec[i] maxFreqVec[i] = maxFreq; } // Print occurrence of maximum // element for each query for (int k : q) { System.out.print( maxFreqVec[k - 1] + " "); } } // Driver Code public static void main(String[] args) { int[] arr = { 5, 4, 5, 3, 2 }; int[] q = { 1, 2, 3, 4, 5 }; // Function Call FreqOfMaxElement(arr, q); }} |
Python3
# Python3 program for # the above approachimport sys;# Function to find occurrence# of max element in given # subarraydef FreqOfMaxElement(arr, q): # Store the frequency of # maximum element maxFreqVec = [0] * (len(arr)); maxSoFar = -sys.maxsize; maxFreq = 0; # Traverse over the array # arr from right to left for i in range(len(arr)-1, -1, -1): # If curr element is # greater than maxSofar if (arr[i] > maxSoFar): # Reset maxSofar # and maxFreq maxSoFar = arr[i]; maxFreq = 1; # If curr is equal to # maxSofar elif (arr[i] == maxSoFar): # Increment the # maxFreq maxFreq += 1; # Update maxFreqVec[i] maxFreqVec[i] = maxFreq; # Print occurrence of maximum # element for each query for i in range(0, len(q)): print(maxFreqVec[q[i] - 1], end = " ");# Driver Codeif __name__ == '__main__': arr = [5, 4, 5, 3, 2]; q = [1, 2, 3, 4, 5]; # Function Call FreqOfMaxElement(arr, q);# This code is contributed by shikhasingrajput |
C#
// C# program for the // above approachusing System;class GFG{ // Function to find occurrence of// max element in given subarraystatic void FreqOfMaxElement(int[] arr, int[] q){ // Store the frequency of // maximum element int[] maxFreqVec = new int[arr.Length]; int maxSoFar = Int32.MinValue; int maxFreq = 0; // Traverse over the array arr[] // from right to left for (int i = arr.Length - 1; i >= 0; i--) { // If curr element is greater // than maxSofar if (arr[i] > maxSoFar) { // Reset maxSofar and maxFreq maxSoFar = arr[i]; maxFreq = 1; } // If curr is equal to maxSofar else if (arr[i] == maxSoFar) { // Increment the maxFreq maxFreq++; } // Update maxFreqVec[i] maxFreqVec[i] = maxFreq; } // Print occurrence of maximum // element for each query foreach (int k in q) { Console.Write(maxFreqVec[k - 1] + " "); }} // Driver codestatic void Main() { int[] arr = {5, 4, 5, 3, 2}; int[] q = {1, 2, 3, 4, 5}; // Function Call FreqOfMaxElement(arr, q); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program for the above approach // Function to find occurrence of// max element in given subarrayfunction FreqOfMaxElement(arr, q){ // Store the frequency of maximum // element var maxFreqVec = new Array(arr.length); var maxSoFar = -1000000000; var maxFreq = 0; // Traverse over the array arr[] // from right to left for(var i = arr.length - 1; i >= 0; i--) { // If curr element is greater // than maxSofar if (arr[i] > maxSoFar) { // Reset maxSofar and maxFreq maxSoFar = arr[i]; maxFreq = 1; } // If curr is equal to maxSofar else if (arr[i] == maxSoFar) { // Increment the maxFreq maxFreq++; } // Update maxFreqVec[i] maxFreqVec[i] = maxFreq; } // Print occurrence of maximum // element for each query q.forEach(k => { document.write( maxFreqVec[k - 1] + " "); });}// Driver Codevar arr = [ 5, 4, 5, 3, 2 ];var q = [ 1, 2, 3, 4, 5 ];// Function CallFreqOfMaxElement(arr, q);// This code is contributed by rutvik_56</script> |
Output:
2 1 1 1 1
Time Complexity: O(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!
… [Trackback]
[…] Information to that Topic: geeksforgeeks.org/queries-to-count-occurrences-of-maximum-array-element-in-subarrays-starting-from-given-indices/ […]