# First element occurring k times in an array

Given an array of n integers. The task is to find the first element that occurs k number of times. If no element occurs k times the print -1. The distribution of integer elements could be in any range.

Examples:

```Input : {1, 7, 4, 3, 4, 8, 7},
k = 2
Output : 7
Both 7 and 4 occur 2 times.
But 7 is the first that occurs 2 times.

Input : {4, 1, 6, 1, 6, 4},
k = 1
Output : -1
```

Simple Approach: By using two loops. It has a time complexity of O(n2).

Efficient Approach: Use unordered_map for hashing as range is not known. Steps:

1. Traverse the array elements from left to right.
2. While traversing increment their count in the hash table.
3. Again traverse the array from left to right and check which element has a count equal to k. Print that element and stop.
4. If no element has a count equal to k, print -1.

Below is the implementation of above approach:

## C++

 `// C++ implementation to find first ` `// element occurring k times ` `#include ` ` `  `using` `namespace` `std; ` ` `  `// function to find the first element ` `// occurring k number of times ` `int` `firstElement(``int` `arr[], ``int` `n, ``int` `k) ` `{ ` `    ``// unordered_map to count ` `    ``// occurrences of each element ` `    ``unordered_map<``int``, ``int``> count_map; ` `    ``for` `(``int` `i=0; i

## Java

 `import` `java.util.HashMap; ` ` `  `// Java implementation to find first ` `// element occurring k times ` `class` `GFG { ` ` `  `// function to find the first element ` `// occurring k number of times ` `    ``static` `int` `firstElement(``int` `arr[], ``int` `n, ``int` `k) { ` `        ``// unordered_map to count ` `        ``// occurrences of each element ` ` `  `        ``HashMap count_map = ``new` `HashMap<>(); ` `        ``for` `(``int` `i = ``0``; i < n; i++) { ` `            ``int` `a = ``0``; ` `            ``if``(count_map.get(arr[i])!=``null``){ ` `                ``a = count_map.get(arr[i]); ` `            ``} ` `             `  `            ``count_map.put(arr[i], a+``1``); ` `        ``} ` `        ``//count_map[arr[i]]++; ` ` `  `        ``for` `(``int` `i = ``0``; i < n; i++) ``// if count of element == k ,then ` `        ``// it is the required first element  ` `        ``{ ` `            ``if` `(count_map.get(arr[i]) == k) { ` `                ``return` `arr[i]; ` `            ``} ` `        ``} ` ` `  `        ``// no element occurs k times ` `        ``return` `-``1``; ` `    ``} ` ` `  `// Driver program to test above ` `    ``public` `static` `void` `main(String[] args) { ` `        ``int` `arr[] = {``1``, ``7``, ``4``, ``3``, ``4``, ``8``, ``7``}; ` `        ``int` `n = arr.length; ` `        ``int` `k = ``2``; ` `        ``System.out.println(firstElement(arr, n, k)); ` `    ``} ` `} ` ` `  `//this code contributed by Rajput-Ji `

## Python3

 `# Python3 implementation to  ` `# find first element  ` `# occurring k times ` ` `  `# function to find the  ` `# first element occurring  ` `# k number of times ` `def` `firstElement(arr, n, k): ` ` `  `    ``# dictionary to count ` `    ``# occurrences of  ` `    ``# each element ` `    ``count_map ``=` `{}; ` `    ``for` `i ``in` `range``(``0``, n): ` `        ``if``(arr[i] ``in` `count_map.keys()): ` `            ``count_map[arr[i]] ``+``=` `1` `        ``else``: ` `            ``count_map[arr[i]] ``=` `1` `        ``i ``+``=` `1` `     `  `    ``for` `i ``in` `range``(``0``, n):  ` `         `  `        ``# if count of element == k , ` `        ``# then it is the required ` `        ``# first element  ` `        ``if` `(count_map[arr[i]] ``=``=` `k): ` `            ``return` `arr[i] ` `        ``i ``+``=` `1` `             `  `    ``# no element occurs k times ` `    ``return` `-``1` ` `  `# Driver Code ` `if` `__name__``=``=``"__main__"``: ` ` `  `    ``arr ``=` `[``1``, ``7``, ``4``, ``3``, ``4``, ``8``, ``7``]; ` `    ``n ``=` `len``(arr) ` `    ``k ``=` `2` `    ``print``(firstElement(arr, n, k)) ` ` `  `# This code is contributed  ` `# by Abhishek Sharma `

Output:

```7
```

Time Complexity: O(n)

## tags:

Arrays Hash Arrays Hash