Queries to count occurrences of maximum array element in subarrays starting from given indices

0 0 8 minutes read

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 subarray
void 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 Code
int 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 approach
 
using 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 subarray
function 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 Code
let arr = [ 5, 4, 5, 3, 2 ];
let q = [ 1, 2, 3, 4, 5 ];
 
// Function Call
FreqOfMaxElement(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 subarray
void 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 Code
int 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 approach
import 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 approach
import sys;
 
# Function to find occurrence
# of max element in given 
# subarray
def 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 Code
if __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 approach
using System;
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 = 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 code
static 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 subarray
function 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 Code
var arr = [ 5, 4, 5, 3, 2 ];
var q = [ 1, 2, 3, 4, 5 ];
 
// Function Call
FreqOfMaxElement(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 zambiatek!