Home » Technical Interview Questions » Hashing Interview Questions » First non Repeating Element

First non Repeating Element


Reading Time - 2 mins

We are given an array A. We have to find the first non repeating element in the array.

Example

Input:

A[]={2,1,2,1,3,4}

Output:

First non-repeating element is: 3

Because 1, 2 is not the answer because they are repeating and 4 is not the answer because we have to find the first non_repeating element, which is 3, not 4.

Approach 1: Brute force

Main idea

For every element in the array, we will iterate the whole array and if this element is non-repeating then we will just print this element.

Algorithm

  1. Run a loop for I in range 0 to n-1
    1. Run a loop for j in range 0 to n
      1. If j becomes equal to n, then print A[i] and return.
      2. If I is not equal to j and A[i] is equal to A[j], then break from this loop.
    2. Print that all the elements are repeating in the array.

Implementation for First non Repeating Element

C++ Program

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (j == n)
            {
                cout << "First non-repeating element is: " << A[i] << endl;
                return;
            }
            if (j != i and A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

JAVA Program

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        int n = A.length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (j == n)
                {
                    System.out.println("First non-repeating element is: "+A[i]);
                    return;
                }
                if (j != i && A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

Complexity Analysis for First non Repeating Element

Time Complexity

We have two nested loops both of size N, so the total time complexity is O(N^2).

READ  Convert an array to reduced form

Space complexity

We are not using any extra space so the space complexity is O(1).

Approach 2: Using hashing

Main idea

We can store the frequency of each element in a hash table and after that we can traverse the array and find the first element whose frequency is 1.

Algorithm

  1. Store the frequency of each element in a hash table.
  2. Run a loop for I in range 0 to n-1
    1. If the frequency of A[i] in the hash table is 1, print A[i] and return.
  3. Print that there all the elements in the array that are repeating.

Understand with example

A[]={2, 1, 2, 1, 3, 4}

Then the hash table will look like this:

First non Repeating Element

Implementation for First non Repeating Element

C++ Program

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            cout << "First non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

JAVA Program

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        java.util.HashMap<Integer, Integer> hash_table = new java.util.HashMap<Integer, Integer>();
        int n = A.length;
        for(int i=0;i<n;i++)
        {
            Integer freq = hash_table.get(A[i]);
            hash_table.put(A[i], (freq == null) ? 1 : freq + 1); 
        }

        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                System.out.println("First non-repeating element is: "+A[i]);
                return;
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

Complexity Analysis for First non Repeating Element

Time Complexity

We are iterating the array only twice so the total time complexity is O(N).

READ  Find pairs with given sum such that elements of pair are in different rows

Space complexity

We are maintaining a hash table so the space complexity is O(N).

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions