1. Introduction
The At Least K Occurrences problem is a common Array and Hashing problem.
Given an integer array arr[] and an integer k, we need to find the first element that occurs at least k times in the array.
If multiple elements satisfy the condition, we must return the element whose k-th occurrence appears earliest in the array.
If no element occurs at least k times, return -1.
We can solve this problem efficiently using a Dictionary (HashMap) and frequency counting.
2. Understanding the Problem
Let's understand the requirement with an example.
Input:
arr = [1, 7, 4, 3, 4, 8, 7]
k = 2
Output:
4
Explanation:
In this array:
Element 1 occurs once.
Element 7 occurs twice.
Element 4 occurs twice.
Element 3 occurs once.
Element 8 occurs once.
Both 7 and 4 occur twice.
However:
Since element 4 reaches the required frequency first, the answer is 4.
Important: We are not looking for the smallest element or the element with the highest frequency. We are looking for the element that reaches its k-th occurrence first.
3. Understanding the Concepts
What is a Dictionary?
A Dictionary is a collection that stores data in key-value pairs.
In this problem:
Example:
Dictionary<int, int> freq = new Dictionary<int, int>();
Suppose the array is:
arr = [1, 7, 4, 4, 7]
The frequency dictionary will eventually contain:
Key (Element) | Value (Frequency) |
|---|
1 | 1 |
7 | 2 |
4 | 2 |
Important Dictionary Operations
Operation | Purpose |
|---|
ContainsKey() | Checks whether a key exists. |
freq[key] = value | Inserts or updates a value. |
freq[key]++ | Increases the frequency. |
TryGetValue() | Retrieves a value safely. |
Dictionary lookup and insertion take O(1) average time.
What is Frequency Counting?
Frequency counting means maintaining the number of times each element appears in an array.
For example:
arr = [2, 3, 2, 4, 2]
Frequency:
2 → 3 times
3 → 1 time
4 → 1 time
Instead of repeatedly traversing the array, we update the frequency while traversing it once.
4. C# Implementation
class Solution
{
public int firstElementKTime(int[] arr, int k)
{
Dictionary<int, int> freq = new Dictionary<int, int>();
for (int i = 0; i < arr.Length; i++)
{
// Initialize frequency if element is not present
if (!freq.ContainsKey(arr[i]))
{
freq[arr[i]] = 0;
}
// Increase the frequency
freq[arr[i]]++;
// Check whether element reaches k occurrences
if (freq[arr[i]] == k)
{
return arr[i];
}
}
// No element occurs at least k times
return -1;
}
}
5. Step-by-Step Code Explanation
Step 1: Create a Dictionary
Dictionary<int, int> freq = new Dictionary<int, int>();
We create a Dictionary to store each unique element and its frequency.
Initially, the Dictionary is empty.
Step 2: Traverse the Array
for (int i = 0; i < arr.Length; i++)
We use a for loop to visit every element from the beginning to the end of the array.
Step 3: Initialize the Frequency
if (!freq.ContainsKey(arr[i]))
{
freq[arr[i]] = 0;
}
We check whether the current element already exists in the Dictionary.
If it does not exist, we initialize its frequency to zero.
Step 4: Increase the Frequency
freq[arr[i]]++;
Whenever an element appears, we increase its frequency by one.
For example:
Element = 4
First occurrence → 1
Second occurrence → 2
Step 5: Check the K-th Occurrence
if (freq[arr[i]] == k)
{
return arr[i];
}
This is the most important condition.
Whenever the frequency becomes equal to k, we immediately return that element.
Why?
Because we traverse the array from left to right. Therefore, the first element to reach frequency k is the element whose k-th occurrence appears earliest.
Step 6: Return -1
return -1;
If the loop finishes without finding an element that occurs at least k times, we return -1.
6. Complete Dry Run
Let's take the example:
arr = [1, 7, 4, 3, 4, 8, 7]
k = 2
Initially:
freq = {}
Index | Element | Frequency Dictionary | Action |
|---|
0 | 1 | {1:1} | Continue |
1 | 7 | {1:1, 7:1} | Continue |
2 | 4 | {1:1, 7:1, 4:1} | Continue |
3 | 3 | {1:1, 7:1, 4:1, 3:1} | Continue |
4 | 4 | {1:1, 7:1, 4:2, 3:1} | Return 4 |
At index 4:
Current Element = 4
Current Frequency = 2
Required Frequency = 2
Condition:
freq[4] == k
2 == 2
The condition is true.
Therefore:
Output = 4
We don't need to process the remaining elements.
7. Another Example – No Element Found
Input:
arr = [10, 8, 2]
k = 10
Frequency:
10 → 1
8 → 1
2 → 1
No element reaches frequency 10.
Therefore:
Output = -1
8. Why Do We Use == k Instead of >= k?
This is an important interview question.
We use:
if (freq[arr[i]] == k)
{
return arr[i];
}
We don't need to check >= k because we return immediately when an element first reaches frequency k.
For example:
arr = [3, 1, 3, 3]
k = 3
The frequency of 3 changes as follows:
First occurrence → 1
Second occurrence → 2
Third occurrence → 3
At the third occurrence, the condition becomes true and the function returns 3.
9. Complexity Analysis
Time Complexity: O(n)
We traverse the array only once.
Dictionary ContainsKey() takes O(1) average time.
Dictionary insertion takes O(1) average time.
Frequency updates take O(1) average time.
Therefore, the overall expected time complexity is O(n), where n is the array length.
Auxiliary Space Complexity: O(n)
In the worst case, every array element is unique.
The Dictionary may store all n elements.
Therefore, the auxiliary space complexity is O(n).
10. Important Interview Questions
Q1. Why do we use Dictionary?
To store each element and its frequency efficiently.
Q2. Why do we traverse only once?
Because we update the frequency while traversing the array. There is no need for a second traversal.
Q3. Why do we return immediately?
Because the first element to reach frequency k has the earliest k-th occurrence.
Q4. What happens if k = 1?
The first element in the array is returned because its first occurrence already satisfies the condition.
Q5. What happens if no element occurs k times?
The function returns -1.
Q6. Can we solve this problem using nested loops?
Yes, but nested loops may take O(n²) time. A Dictionary provides an efficient O(n) average-time solution.
11. Conclusion
The At Least K Occurrences problem can be solved efficiently using a Dictionary and frequency counting.
The main idea is to maintain the occurrence count of every element while traversing the array.
Whenever an element reaches the required frequency k, we immediately return it.
This approach avoids unnecessary comparisons and provides an efficient solution.
Key Takeaways
Understand how Dictionary stores key-value pairs.
Learn frequency counting using HashMap.
Traverse an array using a single loop.
Use early return when the required condition is satisfied.
Remember that the order of occurrence matters in this problem.
Join the conversation! Your thoughts help the community grow.