Problem Solving: First element to occur k times

We'll discuss an efficient solution to the problem of finding the first element that occurs at least k times in an array. We'll analyze the problem, explain the provided solution, and discuss its time and space complexity.

Problem Overview:

Given an array of integers and an integer k, we need to find the first element in the array that occurs at least k times. If there's no such element, we return -1.

Solution Approach:

We can efficiently solve this problem using a hash map (unordered_map in C++). Here's the step-by-step explanation of the solution:

1. Initialize an unordered_map to store the frequency of each element in the array.
2. Iterate through the array.
3. For each element encountered, update its frequency count in the hash map.
4. Check if the frequency count of the current element equals k.
5. If yes, return the current element as it is the first element occurring k times.
6. If no such element is found after iterating through the array, return -1.

Let's implement this solution in code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int firstElementKTime(int n, int k, int a[])
    {
        // Create an unordered map to store frequency of elements
        unordered_map<int, int> mp;

        // Iterate through the array
        for (int i = 0; i < n; i++)
        {
            // Update the frequency of current element
            mp[a[i]]++;
            
            // Check if the frequency becomes equal to k
            if (mp[a[i]] == k)
            {
                // Return the element if condition is met
                return a[i];
            }
        }
        
        // If no such element is found, return -1
        return -1;
    }
};        

Time Complexity Analysis:

The time complexity of this solution is O(n) because we iterate through the array once to calculate the frequency of each element.

Space Complexity Analysis:

The space complexity of this solution is also O(n) because we use an unordered_map to store the frequency of elements in the array.

Conclusion:

We discussed an efficient solution to find the first element occurring at least k times in an array. By using a hash map to store the frequency of elements, we were able to achieve a time complexity of O(n). This solution is optimal and fulfills the requirements of the problem efficiently.