Cracking the coding interview: Find element to occur K times — 5

Steven Lu
1 min readJul 23, 2022

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 :
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)

1 <= N, K <= 105
1<= A <= 106


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.