Solution: First Non-Repeating Integer in an Array—Hashing

Statement

Given an array of integers, nums, find the first non-repeating integer in the array.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$

• $-5000 \leq$ nums[i] $\leq 5000$

Solution

We track the frequency of each element in the array using a hash map, which stores key-value pairs. The keys represent the elements of the array, and the values indicate how many times each element occurs.

1. Initialize an empty hash map, counts, to store the counts of each element.

2. Iterate through the array of elements.

   1. If the element is already a key in counts, increment its value by $1$ to represent its count.

   2. If the element is not in counts, add it to the dictionary with a count of $1$.

3. Iterate through the array again.

   1. Check the count of each element in counts.

   2. Return the first element with a count of $1$.

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