First non Repeating Element

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).

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:

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).

Space complexity

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

References