First element occurring k times in an array

We have given a number ‘k’ and an integer array. The problem “First element occurring k times in an array” says to find out the first element in the array which occurs exactly k times in an array. If there is no element in the array which occurs k times then return -1.

Example

Arr[]={1,4,5,2,4,2,7},  k=2

4

Explanation

In this example, there are two elements that occur k times. 4 and 2 exist exactly k number of times, but 4 is the first that occurs k times. So we return 4.

Algorithm

1. Declare a HashMap.
2. Traverse the array.
   • Count and store the frequency of each element of the array into the map.
3. Again traverse the array and check if each array element’s frequency is equal to k.
   • If the condition satisfies, then return the element.

Explanation

We have our input values as integer array and an integer k. The problem statement asks to find out the first element in an array that occurs exactly k times. To solve this problem, we are going to use Hashing. Hashing is the possible way through which we can reduce our time complexity. It costs O(n) time complexity.

We will count and store the frequency of each element in our map. Suppose an element comes 3 times in an array we set its frequency as 3, along with that element. HashMap can be used for this purpose for storing keys and values. We will be storing all the elements as keys and their frequencies as values in a HashMap. Then we will run a loop and traverse an array and pick each element and check their frequency. If any element’s frequency is found to be equal to k, then we will return that element. Since we are traversing the array, so if element found with the occurrence k times. Then definitely it will be the first element with k no of occurrences.

Let us consider an example:

arr[] = {2,4,6,4,2,1,}, k=2

We will be storing elements as keys and their frequencies as values into the map, after storing our map will have the following values:

myMap={1:1, 2:2, 4:2, 6:1};

We will check each array element, starting from 0th index we will start traversing the array

i=0,

if frequency of each array[i]==k:

Frequency of 2 is 2, which is equal to k also it the element which comes first with k no of occurrences, so we return the arr[i] and our output would be 2.

In case if any of the element’s frequency would not match with ‘k’, then we will return -1.

Code

C++ code to find First element occurring k times in an array

#include<iostream>
#include <unordered_map>

using namespace std;

int firstElement(int arr[], int n, int k)
{
    unordered_map<int, int> freqMap;

    for (int i=0; i<n; i++)
        freqMap[arr[i]]++;

    for (int i=0; i<n; i++)
        if (freqMap[arr[i]] == k)
            return arr[i];

    return -1;
}
int main()
{
    int arr[] = {2,4,6,4,2,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}

2

Java code to find First element occurring k times in an array

import java.util.HashMap;

class firstKOccuringElement
{
    public static int getFirstElement(int arr[], int n, int k)
    {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(freqMap.containsKey(arr[i]))
            {
                freqMap.put(arr[i], freqMap.get(arr[i])+1);
            }
            else
            {
                freqMap.put(arr[i], 1);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (freqMap.get(arr[i]) == k)
            {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,6,4,2,1,6};
        int n = arr.length;
        int k = 2;
        System.out.println(getFirstElement(arr, n, k));
    }
}

2

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Here, since we have used a hashmap we were able to perform operations in O(1) time.

Space Complexity

O(n) where “n” is the number of elements in the array. In the worst case when all elements are distinct. We’ll have to store all N elements into the map which will take linear space.