Frequency of Maximum Value HackerRank Problem:-
The question was appeared in coding test of one of the company on HackerRank.
Task:- Given an array ‘nums’ of length N containing positive integers and an array ‘query’ of length ‘Q’ containing indexes, print/store for each query the count of maximum value in the sub-array starting at index ‘i’ and ending at index ‘N-1’.
For eg:- nums = [ 5, 4, 5, 3, 2 ] and query = [ 1, 2, 3, 4, 5 ]
Answer would be [ 2, 1, 1, 1, 1 ].
For the first query, we have to find the count of maximum value( which is 5) in the subarray [ 5, 4, 5, 3, 2 ], which is 2.
For the second query, the count of maximum value(which is 5) in the subarray [4, 5, 3, 2 ], which is 1.
Similarly, for the fourth query, the count of maximum value(which is 3) in the subarray [ 3, 2 ].
Note that the index given in the query array is 1-based indexing.
Brute Force Approach:- The simplest way to solve this would be to traverse from index ‘i’ to index ‘N-1’ to get the maximum value in the subarray. Then we traverse in the same subarray to calculate the count of this maximum value. We do this for each query.
The time complexity of this approach would be O(N*Q) as we are traversing subarray 2 times i.e- O(2*N) for Q queries, so the time complexity becomes O(2*N*Q), but the overall time complexity remains O(N*Q).
Brute Force Code:-
One liner in Python:-
Note that the above code does the same thing as our brute force code.
Efficient Approach:- Instead of traversing the array from left to right again and again, we can traverse from right to left once. While traversing we can calculate and store the answer for each index.
We keep track of the current maximum value and the count of current maximum.The three conditions that can arise are:
- If we encounter a number equal to the current maximum, we increment the counter and store it.
- If we encounter a number greater than the current maximum, we update the maximum and reset our counter to 1 and store it.
- If we encounter a number less than the current maximum, the answer remains the same, neither the count is incremented nor the maximum is updated. Store the same count in the array.
Then we can simply traverse the query array and get the required answer for a particular index from our stored array.
The time complexity would be O(N+Q) as we traverse both the arrays only once. The space complexity would be O(N) to store the array in which all the answers are present.
Efficient Code:-
Check out other interesting interview/coding questions:-
Don’t forget to follow to show support & keep getting updates.
