Given an array of N integers. Find the first element that occurs atleast K number of times.
Example 1:
Input :
N = 7, K = 2
A[] = {1, 7, 4, 3, 4, 8, 7}
Output :
4
Explanation:
Both 7 and 4 occur 2 times.
But 4 is first that occurs 2 times.Your Task:
You don’t need to read input or print anything. Your task is to complete the function firstElementKTime() which takes the array A[], its size N and an integer K as inputs and returns the required answer. If answer is not present in the array, return -1.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N, K <= 105
1<= A <= 106
Solution:
Time complexity: O(n)
Space complexity: O(n)
The tactic of addressing the question is to apply Hashmap to store key-value, which is both index value and its occurrence times. While counting the maximum frequency of index value, if it is equal to k, then return it. Or, add the new index into Hashmap as 1.
