First element occurring k times in an array

Introduction

In this article, we are going to learn how we can find the first occurrence an element k times in an array with the help of hashmap. 

A Hash table is one of the essential data structures that uses a particular function known as a hash function that maps a given value with a key to retrieve the elements faster.

A hash table is one of the data structures used to store information. The information is composed of keys and values. The hash table can be implemented with the help of an associative array. The effectiveness of the hash function used for mapping determines how efficient the mapping process is.

Problem Statement

The problem statement is that we need to find the first element in the array that is occurring or repeating k times the array.

Sample Examples

Input:  [5,2,2,12,12,1] k=2

Output: 2

Explanation

Approach

In order to find the first occurrence of the element in an array k times. We will use the hashmap approach to find the solution that is efficient. We are going to create a hashmap with a key value pair of array elements and occurrence of those elements. After that we will iterate a loop and compare the value of k with the hash key values until we find the first occurrence.

Algorithm

• Start
• Declare an array of name ar[ ] with n elements
• Create a hashmap for the same datatype of the array
• Take input of k
• Loop n times and map the values of occurrences with their respective element
• Loop n times and compare the value of k with hash key value until we find the first element.
• Store the element in variable named result
• Display the result on screen
• End

Implementation

C++

#include<bits/stdc++.h>
using namespace std;
 int main()
 {
     int ar[] = {1,5,4,4,6,7,5,3,3};
     int k,result=-1;
     
     /* calculate the size of given array */
     int size = sizeof(ar)/sizeof(ar[0]);
     
     /* printing the given array */
     cout<<"Given array: "<<endl;
     for(int i=0;i<size;i++)
     {
         cout<<ar[i]<<" ";
     }


/* create an unordered map */
     unordered_map<int,int> test;
     cout<<"\nEnter the value of k: ";
     cin>>k;


/* calculating the occurrence and storing as values */
     for(int i=0;i<size;i++)
     {
         test[ar[i]]++;
     }


/* comparing and finding the first occurence*/
     for(int i=0;i<size;i++)
     {
         if(test[ar[i]]==k)
         {
             result = ar[i];
             break;
         }
     }


/* printing the result  */
     cout<<"first Element occuring K times: "<<result<<endl;
     return 0;
 }

You can also try this code with Online C++ Compiler

Run Code

Python

if __name__ == '__main__':
    #given array
    ar = [1,5,4,4,6,7,5,3,3,3]
    result = -1
    
    #calculating size of given array
    size = len(ar)
    
    #printing the array
    print("Given array:",ar)
    
    #create hashmap
    test = {}


    #taking input
    k = int(input("Enter the value of k: "))


    #mapping values
    for i in range(0,size):
        if(ar[i] in test.keys()):
            test[ar[i]]+=1
        else:
            test[ar[i]] = 1


     #checking the occurrence
    for i in range(0,size):
        if(test[ar[i]] == k):
            result = ar[i]
            break


    print("first element occuring k times:",result)

You can also try this code with Online Python Compiler

Run Code

Java

import java.util.*;
class Main {
  static int firstElement(int ar[], int size, int k) {

    /*unordered_map to count
    occurrences of each element */
    HashMap < Integer, Integer > test = new HashMap < > ();
    for (int i = 0; i < size; i++) {
      int a = 0;
      if (test.get(ar[i]) != null) {
        a = test.get(ar[i]);
      }
      test.put(ar[i], a + 1);
    }

    /* if count of element == k ,then*/
    for (int i = 0; i < size; i++)

    /*t is the required first element*/
    {
      if (test.get(ar[i]) == k) {
        return ar[i];
      }
    }
    /* no element occurs k times*/
    return -1;
  }

  public static void main(String[] args) {
    int ar[] = {1,5,4,4,6,7,5,3,3};
    int size = ar.length;

    /* printing the given array */
    System.out.println("Given array:");
    for (int i = 0; i < size; i++) {
      System.out.print(ar[i] + " ");
    }
    System.out.println("\nEnter the value of k:");
    Scanner s = new Scanner(System.in);
    int k = s.nextInt();
    System.out.println("first element occuring k times:");
    System.out.println(firstElement(ar, size, k));
  }
}

You can also try this code with Online Java Compiler

Run Code

Input:  [1,5,4,4,6,7,5,3,3,3] k=2

Output:

If the element is not present in the array that is repeating k times then the program will return -1 as an output.

Time Complexity

Every iteration in the above programs is done in n times of the given array. Whether it is to print to or to map the values with the elements of the array it is looped in n times. So that is why the time complexity is:

O(n) here n is the size of the given array 

Space Complexity

O(n) here n is the size of the hashmap.
You can also read about the Longest Consecutive Sequence.