First Element that occur K times in an array

Given an array of integers and an integer k, find the first element that occurs exactly k times in the array. If no such element exists, return -1.

Input/Output Examples

plaintext

Example 1:
Input:
arr = [1, 7, 4, 3, 4, 8, 7]
k = 2
Output: 7
Explanation: The element 7 is the first element that occurs exactly 2 times.

Example 2:
Input:
arr = [1, 2, 2, 3, 1, 4, 4, 5]
k = 2
Output: 1
Explanation: Both 1 and 2 occur exactly 2 times, but 1 is the first to reach 2 occurrences.

Example 3:
Input:
arr = [2, 2, 3, 3, 5]
k = 3
Output: -1
Explanation: No element occurs exactly 3 times, so the output is -1.

Approach to find the first element that occur K times

Count Frequencies:
- Use a hash map (or dictionary) to keep track of the frequency of each element as you iterate through the array.
Check for Exact Occurrence of K:
- As you update the count for each element, immediately check if it reaches exactly k occurrences.
- Return the element once it meets the condition of occurring k times.
Return -1 if No Element Occurs K Times:
- If the end of the array is reached without any element occurring exactly k times, return -1.

C++ Program to find the first element that occur K times

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Function to find the first element to occur k times
int firstElementKTimes(const vector<int>& arr, int k) {
    unordered_map<int, int> frequencyMap;

    // Count frequencies and check for first element to reach k occurrences
    for (int num : arr) {
        frequencyMap[num]++;
        if (frequencyMap[num] == k) {
            return num;
        }
    }

    return -1; // No element found with k occurrences
}

int main() {
    vector<int> arr = {1, 7, 4, 3, 4, 8, 7};
    int k = 2;
    cout << "First element to occur " << k << " times: " << firstElementKTimes(arr, k) << endl;
    return 0;
}

Java Program to find the first element that occur K times

java

import java.util.HashMap;

public class FirstElementKTimes {

    // Function to find the first element to occur k times
    public static int firstElementKTimes(int[] arr, int k) {
        HashMap<Integer, Integer> frequencyMap = new HashMap<>();

        // Count frequencies and check for first element to reach k occurrences
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
            if (frequencyMap.get(num) == k) {
                return num;
            }
        }

        return -1; // No element found with k occurrences
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, 4, 3, 4, 8, 7};
        int k = 2;
        System.out.println("First element to occur " + k + " times: " + firstElementKTimes(arr, k));
    }
}

Python Program to find the first element that occur K times

python

# Function to find the first element to occur k times
def first_element_k_times(arr, k):
    frequency_map = {}

    # Count frequencies and check for first element to reach k occurrences
    for num in arr:
        frequency_map[num] = frequency_map.get(num, 0) + 1
        if frequency_map[num] == k:
            return num

    return -1 # No element found with k occurrences

# Example usage
if __name__ == "__main__":
    arr = [1, 7, 4, 3, 4, 8, 7]
    k = 2
    print("First element to occur", k, "times:", first_element_k_times(arr, k))

Time Complexity

O(n): The array is traversed once, and updating the frequency map is O(1) per element on average.

Space Complexity

O(n): Additional space is needed to store the frequency of each unique element in the hash map.