Find First Non-Repeating Element in an Array in C++

In this article, we will write a program to find the first non-repeating element in the given array in C++.

Example

Input: arr[] = {2, 3, 4, 5, 2, 5, 4, 1, 3}
Output: 1

Input: arr[] = {1, 2, 3, -1, 1, 3, 2, 4}
Output: -1

Get the First Non-Repeating Element in an Array in C++

Method 1: Using two nested loops

1. Traverse the array arr as an outer loop.

  • Iterate the array from range 0 to n as an inner loop
  • Now check if (i != j && arr[i] == arr[j]) then break the loop.
  • Else if (j == n) then return arr[i]
#include <bits/stdc++.h>
using namespace std;
int firstNonRepEle(int arr[], int n){
    for (int i = 0; i < n; i++) { 
        int j; 
        for (j = 0; j < n; j++) 
            if (i != j && arr[i] == arr[j]) 
                break; 
        if (j == n) 
            return arr[i]; 
    } 
    return -1; 
}
int main(){
    int arr[] = { 1, 2, 3, 4, 3, 9, 2, 3, 4, 1 }; 
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<firstNonRepEle(arr, n);
    return 0;
}

Output

9

Method 2: Using Hashing

1. First create a hashmap, hm to store the frequency of each element of the given array.

2. Traverse the array and insert the element in hm with their count.

3. Now, traverse the array again and the print element with the count equal to 1.

int firstNonRepEle(int arr[],int n){
    unordered_map<int, int> hm;
    for(int i=0;i<n;i++){
        hm[arr[i]]++;
    }
    for(int i=0;i<n;i++){
        if(hm[arr[i]] == 1)
            return arr[i];
    }
    return -1;
}
int main(){
    int arr[] = {34, 2, 3, 13, 13, 2, 3, 34, 23, 2, 3}; 
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<firstNonRepEle(arr, n);
    return 0;
}

Output

23

Also, read

Leave a Reply

Your email address will not be published.