Find the first non-repeating element in a given array of integers

We are given an array of $N$ integers, and find the first non-repeating element in this array.

Example 1

Input: {1, 2, 3, 1, 2, 3, 4}

Output: 4

In this array, $1$ , $2$ and $3$ are repeating and $4$ is the first non-repeating element.

Example 2

Input: {1, 2, 3, 1, 3, 5}

Output: 2

In this array, $1$ and $3$ are repeating and $2$ and $5$ are non-repeating elements. As $2$ appears first in the array, we return $2$ .

The corner cases of this problem are as follows:

Example 3

Input: {-1, -2, 0, 2, 3}

Output: -1

There are no repeated elements in this array. Therefore, we return the first element of the array as it is the first non-repeating element.

Example 4

Input: {-1, -2, -3, -1, -2, -3}

Output: No non-repeating elements.

All elements are repeated in this array. Therefore, there are no non-repeating elements, and we print that on the screen.

Algorithm

We iterate the entire array from left to right and check every element for repetitions. If we find a repetition, we move to the next element and repeat the same process.

If we do not find any repetition for an element, then we return that element because that is the first non-repeating element in the array.
If we do not find any non-repeating element, we print an appropriate message on the screen.

Code example

Let's look at the code below:

#include <iostream>
using namespace std;
int firstNonRepeatingElem(int arr[], int len) {
  for(int i = 0; i < len; i++)  // iterates over every element of the array
    for(int j = 0; j < len; j++) {  // checks if that element is repeating in the array
      if(arr[i] == arr[j] && i != j)  // breaks the loop if a repeating element is found
        break;
      
      if(j == len - 1)  // if we reach the last index of the array and
        return i;       // haven't found a repetition for the element at index i,
    }                   // then we return the index i
    return -1;  // if all the elements in the array are repeating then we return a -1 flag.
}
// Driver code
int main() {
  int inp_arr[] = {1, 2, 3, 1, 2, 3, 4};
  int length = sizeof(inp_arr)/sizeof(int);
  int answer = firstNonRepeatingElem(inp_arr, length);  // calling our function
  if(answer == -1)  // if the flag is returned, we print the following line.
    cout << "No non-repeating elements.";
  else
    cout << inp_arr[answer];  // if a non-repeating element is found, we return the element at
  return 0;                   // the index returned from the function.
}

Code explanation

Line 5–6: The outer for loop iterates over the entire array and the inner for loop checks the repetition of that element in the array.
Lines 7–8: If a repeating element is found, this if condition breaks the loop and moves to the element at next index to check for repetition.
Lines 10–11: If no repetition is found for the element at index i, then we return that index of the array (as it is the first non-repeating element).
Line 14: If all of the elements in the array are repeating, then we return a -1 flag to indicate that no non-repeating elements are found.
Lines 24–27: Our function returns the index of the array at which the non-repeating element is present or it returns a -1 flag if all elements are repeating. This if condition checks for the flag and prints the appropriate result on the screen.

Time complexity

We iterate over the array of $N$ elements in the outer loop, and then we iterate over the entire array for every element. Thus, the time complexity of this algorithm is $O(N^2).$

Space complexity

We did not use any temporary data structures to store intermediate results. So, the space complexity of this algorithm is $O(1).$

Free Resources