Solution: First Non-Repeating Integer in an Array

Let’s solve the First NonRepeating Integer in an Array problem.

We'll cover the following

Statement

Given an array nums, find the first nonrepeating integer in it.

Constraints:

  • 11 \leq nums.length 103\leq 10^3

  • 104-10^4 \leq nums[i] 104 \leq 10^4

Solution

The brute force approach involves comparing elements pairwise in the array to check if a given element is unique. Here are the steps of the algorithm:

  1. Traverse the array with the pointer p1 from the beginning to the end.

  2. For each element pointed by p1, initialize another pointer, p2, to the start of the array.

  3. Use p2 to traverse the array from the beginning to the end. During this traversal, check if the elements at the locations pointed by p1 and p2 are the same, ensuring p1 and p2 are not pointing to the same location.

  4. If an element pointed by p1 is found to be equal to an element pointed by p2 (where p1 does not point to the same location as p2), it indicates that the element at p1 is not unique. Break the inner loop (the traversal with p2) and move p1 to the next element to restart the check for uniqueness.

  5. If p2 completes its traversal (reaches the end of the array) without finding a duplicate, the element at p1 is unique. We can then return this element.

  6. Repeat this process until p1 has traversed the entire array.

Let’s look at the illustrations below to better understand the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.