Queries to count occurrences of maximum array element in subarrays starting from given indices
Last Updated :
27 Jan, 2023
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);
}
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);
}
}
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# 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 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);
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 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 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# 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
<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>
Time Complexity: O(N)
Auxiliary Space: O(N)
Similar Reads
Queries to find maximum sum contiguous subarrays of given length in a rotating array
Given an array arr[] of N integers and Q queries of the form {X, Y} of the following two types: If X = 1, rotate the given array to the left by Y positions.If X = 2, print the maximum sum subarray of length Y in the current state of the array. Examples: Input: N = 5, arr[] = {1, 2, 3, 4, 5}, Q = 2,
13 min read
Maximum length of same indexed subarrays from two given arrays satisfying the given condition
Given two arrays arr[] and brr[] and an integer C, the task is to find the maximum possible length, say K, of the same indexed subarrays such that the sum of the maximum element in the K-length subarray in brr[] with the product between K and sum of the K-length subarray in arr[] does not exceed C.
15+ min read
Javascript Program for Queries to find maximum sum contiguous subarrays of given length in a rotating array
Given an array arr[] of N integers and Q queries of the form {X, Y} of the following two types: If X = 1, rotate the given array to the left by Y positions.If X = 2, print the maximum sum subarray of length Y in the current state of the array. Examples:Â Input: N = 5, arr[] = {1, 2, 3, 4, 5}, Q = 2,
5 min read
Count of subarrays starting or ending at an index i such that arr[i] is maximum in subarray
Given an array arr[] consisting of N integers, the task is to find the number of subarrays starting or ending at an index i such that arr[i] is the maximum element of the subarray. Examples: Input: arr[] = {3, 4, 1, 6, 2}Output: 1 3 1 5 1Explanation: The subarray starting or ending at index 0 and wi
11 min read
Maximum occurring element in a subarray range (Mode queries)
Given an array arr[] of N integers, and an array Q[] of M pairs, where a pair represents a query of the form {L, R}, the task is to find the maximum occurring element in the range [L, R] and its frequency for each query. If there are multiple elements with maximum frequency, then print the maximum e
15 min read
Largest interval in an Array that contains the given element X for Q queries
Given an array arr[] of N elements and Q queries of the form [X]. For each query, the task is to find the largest interval [L, R] of the array such that the greatest element in the interval is arr[X], such that 1 ? L ? X ? R. Note: The array has 1-based indexing. Examples: Input: N = 5, arr[] = {2,
10 min read
Rearrange Array to maximize sum of MEX of all Subarrays starting from first index
Given an array arr[] of N elements ranging from 0 to N-1(both included), the task is to rearrange the array such that the sum of all the MEX from every subarray starting from index 0 is maximum. Duplicates can be present in the array. MEX of an array is the first non-negative element that is missing
8 min read
Queries to count subarrays consisting of given integer as the last element
Given an array arr[] and an array query[] consisting of Q queries, the task for every ith query is to count the number of subarrays having query[i] as the last element. Note: Subarrays will be considered to be different for different occurrences of X. Examples: Input: arr[] = {1, 5, 4, 5, 6}, Q=3, q
11 min read
Maximize score of same-indexed subarrays selected from two given arrays
Given two arrays A[] and B[], both consisting of N positive integers, the task is to find the maximum score among all possible same-indexed subarrays in both the arrays such that the score of any subarray over the range [L, R] is calculated by the maximum of the values (AL*BL + AL + 1*BL + 1 + ... +
15+ min read
Split array into maximum subarrays such that every distinct element lies in a single subarray
Given an array, arr[] of size N, the task is to split the array into the maximum number of subarrays such that the first and the last occurrence of all distinct array element lies in a single subarray. Examples: Input: arr[] = {1, 1, 2, 2}Output: 2Explanation:Split the array into subarrays {1, 1} an
6 min read