Home » Data Structure » Hashing Coding Problems

# First element occurring K times in the array using hashing

Here, we are going to see how efficiently we can use the hash data structure to **find the first element occurring K times in the array**?

Submitted by Radib Kar, on July 02, 2020

Prerequisite: Hashing data structure

**Problem statement:**

Find the first element occurring *K* times in the array.

**Example:**

Input array= [2, 3, 2, 3, 2, 3] K=3 The first element occurring k times is 2. Though both 2 and 3 have occurred 3 times since 2 came first, so the answer would be 2 Input array= [1 2 3 1 2] K=3 None of the elements has occurrences 3, so the answer would be -1.

**Solution:**

We can solve this problem using a hash map (hash table). One thing is clear that to find out the first element occurring k times we need to keep track of frequencies for each unique key.

So how can we design the problem with the hash table and what will be the hash function?

Okay, so here each element is our key and the hash table is has the size of the range of the array. So, if the range of the array is *[0,99]* then the hash table size would be 100.

What will be our hash function and how would we map the keys to the corresponding location in the hash table?

The hash function *h(x)=x* here but instead of storing the key itself using linear probing, we will keep the frequency only as we only require that.

So, for example, if we have three 2s as our key, the hash table will store the count (frequency) at location 2.

So, after the hash table is created,

We can check the frequency for each element starting from left to right, one by one. The one satisfying the constraint, i.e., having frequency k will be our answer. In this way, we will get the first element occurring k times. And if none of the elements satisfies then the answer would be -1.

So the algorithm will be,

**Step 1:**

Create the hash table like below: Initially hash table is empty For each key in input array: Hash[key]++

**Step 2:**

For each element e: if(hash[e]==k) return e; End for

**Dry run with the example:**

Input array is = [2, 3, 2, 3, 2, 3] K=3 After creating the hash table as step1 we will have Index Value 2 3 3 3 Now step2 While scanning for first element having frequency K 2 has frequency 3 and thus we return 3 immediately. For example 2: Input array= [1 2 3 1 2] K=3 After creating the hash table as step1 we will have Index Value 1 2 2 2 3 1 So after scanning we find that none of the elements has frequency 3, thus answer will be -1.

**C++ implementation:**

// C++ program to find first element // occurring k times in the array #include <bits/stdc++.h> using namespace std; int first_element(vector<int> arr, int n, int k) { //create a hash table where for each key //the hash function is h(x)=x //we will use stl map as hash table and //will keep frequencies stored //so say two keys are mapping to the same location, //then the location will have value 2 //instead of the keys itself map<int, int> hash; //for each number for (auto i : arr) { hash[i]++; } //now for any number if we find //it has frequency k, we simply return for (auto i : arr) { if (hash[i] == k) return i; } //otherwise return -1 return -1; } int main() { int n, k; cout << "Enter number of elements\n"; cin >> n; cout << "Enter k\n"; cin >> k; vector<int> arr(n, 0); cout << "Input the array elements\n"; for (int i = 0; i < n; i++) { cin >> arr[i]; } cout << "Minimum number of operations required to make all elements same is: "; cout << first_element(arr, n, k) << endl; return 0; }

**Output:**

RUN 1: Enter number of elements 6 Enter k 3 Input the array elements 2 3 2 3 2 3 Minimum number of operations required to make all elements same is: 2 RUN 2: Enter number of elements 5 Enter k 3 Input the array elements 1 2 3 1 2 Minimum number of operations required to make all elements same is: -1

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions