Online Majority Element In Subarray

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
7 upvotes
Asked in companies
SamsungAmdocs

Problem statement

You are given an array ‘ARR’, and you are supposed to answer 'Q' queries. In each query you have three integers, ‘L’, ‘R’, and ‘X’. You are supposed to find if there exists an element in the subarray [ARR[L], ARR[L+1], …, ARR[R-1], ARR[R] that occurs at least ‘X’ number of times under the following conditions:

1. 0 <= L <= R < N, where L is the left-most index of the subarray, R is the right-most index of the subarray, and N is the number of elements in the array ‘ARR’.

2. 2 * X> R - L + 1 i.e. the threshold is always greater than the majority length of the subarray.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line contains an integer ‘N’, which denotes the number of elements in the array ‘ARR’.

The second line contains 'N' integers denoting the elements of the array ‘ARR’.

The third line contains an integer ‘Q’, which denotes the number of queries for the given array.

The next 'Q' lines contain three integers, ‘L’, ‘R’, and ‘X’, where 'L' is the left-most index of the subarray, 'R' is the right-most index of the subarray, and ‘X’ is the threshold value for the given query.
Output Format: 
For each test case, return the majority elements if it exists. Otherwise, return -1.
Note: 
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints: 
1<= T <= 50
1 <= N <= 2* 10^4
1 <= ARR[i] <= 2* 10^4 
1 <= Q <= 10^4
0 <= L <= R < N

Time Limit: 1 sec
Sample Input 1:
2
6
2 2 1 1 2 2
3
0 5 4
0 3 3
2 3 2
6
1 2 3 4 5 6
3
0 5 4
0 3 3
2 3 2
Sample Output 1:
2
-1
1
-1
-1
-1
Explanation for Sample Input 1:
In the first test case, the array elements are [2, 2, 1, 1, 2,2].

In the first query, we have to find a number from indices 0 to 5 that occur at least 4 times. In this range, 2 satisfies the conditions.

In the second query, we have to find a number from indices 0 to 3 that occur at least 3 times. In this range, no number satisfies the condition. So, the answer is -1.

In the third query, we have to find a number from indices 2 to 3 that occur at least 2 times. In this range, 1 satisfies the conditions.

In the second test case, the array elements are [1, 2, 3, 4, 5, 6].

In the first query, we have to find a number from indices 0 to 5 that occur at least 4 times.  In this range, no number satisfies the condition. So, the answer is -1.

In the second query, we have to find a number from indices 0 to 3 that occur at least 3 times. In this range, no number satisfies the condition. So, the answer is -1.

In the third query, we have to find a number from indices 2 to 3 that occur at least 2 times.  In this range, no number satisfies the condition. So, the answer is -1.
Sample Input 2:
2
10
2 2 1 2 1 2 2 1 1 2
4
2 5 4
0 5 6
0 1 2
2 3 2
10
2 2 1 2 1 2 2 1 1 2
4
6 6 1
0 3 3
4 9 6
4 8 4
Sample Output 2:
-1
-1
2
-1
2
2
-1
-1
Hint

Can you traverse over the given sub-array and find the count of every element?

Approaches (3)
Brute Force

The idea is to traverse over the given sub-array and store the count of every element in a hash map. Then, traverse over the hashmap, if the count of any element is greater than the threshold, return that element.

  1. Preprocessing(arr):
  • Declare an array 'NUMS'.
  • Equate 'NUMS' equals to 'ARR' that is passed into this function.
  1. findMajorityElement(L, R, X):
  • Declare a hashmap 'COUNT_OCCURENCES' that stores the count of all integers in the sub-array ‘L’ to ‘R’.
  • Iterate over the array from i = L to R:
    • Increment the count of the current element in the hashmap 'COUNT_OCCURENCES'.
  • Iterate over the hashmap 'COUNT_OCCURENCES' and if the occurrence of any integer is more than ‘X’, return the integer as the final answer.
  • Otherwise, return -1.
Time Complexity

O(N*Q), where ‘N’ is the number of elements in the array and ‘Q’ is the number of queries.

 

Preprocessing: O(1) time

 

SubarrayMajorityFinder: O(N) time.

 

As we are iterating over the given sub-array that may take O(N) in the worst case. Hence the overall time complexity for all the queries is O(N*Q).

Space Complexity

O(N), where ‘N’ is the number of elements in the array.

 

As we are storing the count of every element in a hash map that may grow up to size ‘N’ in the worst case. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Online Majority Element In Subarray
Full screen
Console