« back

Yet another query problem

Tags : geeksforgeeks, array, prefix-sum, hash, cpp, medium

Problem Statement - link #

You are given an array of N elements and num queries, In each query you are given three numbers L,R and K and you have to tell, how many indexes are there in between L and R(L<=i<=R) such that the frequency of a[i] from index i to n-1 is k.

Note: 0-based indexing

Your Task:

You don’t need to read input or print anything. Your task is to complete the function solveQueries() which take two variable N and num representing the length of the original array and number of queries and two arrays as input, A and Q representing the original array and an array of queries(2-D array with 3 columns of L,R and K respectively), and returns the array of length num with the solution to each query.

Expected Time Complexity: O(N^2)
Expected Auxiliary Space: O(N^2)

Examples #

Example 1:

Input:
N=5
num=3
A=[1,1,3,4,3]
Q=[[0,2,2],[0,2,1],[0,4,2]]
Output:
2 1 2
Explanation:
For query 1: 0 2 2
L=0,R=2,K=2
let, L<=i<=R
For i=0: frequency of a[i] i.e. 1 from i to n-1 is 2.
For i=1: frequency of a[i] i.e. 1 from i to n-1 is 1.
For i=2: frequency of a[i] i.e. 3 from i to n-1 is 2.
Hence we have two elements from index 0 to 2 
whose frequency from i to n-1 is 2.

For query 2: 0 2 1
L=0,R=2,K=1
As we can see from the above query that there is 
only a single element in 0 to 2 whose frequency 
from i to n-1 is 1.

For query 3: 0 4 2
The answer will be 2 because of the index 0 and 2.

Example 2:

Input:
N=5
num=2
A=[1,1,1,1,1]
Q=[[0,4,2],[0,4,1]]
Output:
1 1 
Explanation: 
For query 1: 0 4 4 
L=0,R=4,K=4 
let, L<=i<=R 
For i=0: frequency of a[i] i.e. 1 from i to n-1 is 5. 
For i=1: frequency of a[i] i.e. 1 from i to n-1 is 4. 
For i=2: frequency of a[i] i.e. 1 from i to n-1 is 3.
For i=3: frequency of a[i] i.e. 1 from i to n-1 is 2.
For i=4: frequency of a[i] i.e. 1 from i to n-1 is 1. 
Hence we have one elements from index 0 to 4 whose frequency from i to n-1 is 2. 

Similarly For query 2: 
there is only 1 element in 0 to 4 whose frequency from i to n-1 is 1.

Constraints #

Solutions #


class Solution {
  public:
    long long maxTripletProduct(long long arr[], int n)
    {
    	// Complete the function
    	long long mn1 = INT_MAX, mn2 = INT_MAX, mx1 = INT_MIN, mx2 = INT_MIN, mx3 = INT_MIN;
    	for(int i = 0; i < n; i++) {
    	    if(arr[i] < mn1) {
    	        mn2 = mn1;
    	        mn1 = arr[i];
    	    }
    	    else if(arr[i] < mn2) {
    	        mn2 = arr[i];
    	    }
    	    if(arr[i] > mx1) {
    	        mx3 = mx2;
    	        mx2 = mx1;
    	        mx1 = arr[i];
    	    }
    	    else if(arr[i] > mx2) {
    	        mx3 = mx2;
    	        mx2 = arr[i];
    	    }
    	    else if(arr[i] > mx3) {
    	        mx3 = arr[i];
    	    }
    	} 
    	return max((mn1 * mn2 * mx1), (mx1 * mx2 * mx3));
    }
};