An in-depth piece exploring building a modular event-driven microservices architecture, using Spring and Orkes Conductor for orchestration:

# Find the First Non-repeating Element of a List

Last updated: February 12, 2024

## 1. Introduction

In this tutorial, we’ll explore the problem of finding the first non-repeating element in a list. We’ll first understand the problem statement and then implement a few methods to achieve the desired outcome.

## 2. Problem Statement

Given a list of elements, the task is to find the first element that doesn’t repeat in the list. In other words, **we need to identify the first element that appears only once in the list.** If there are no non-repeating elements, we then return an appropriate indication, e.g., *null*.

## 3. Using *for* Loop

This method uses nested *for* loops to iterate through the list and check for repeating elements. It’s straightforward but less efficient.

### 3.1. Implementation

First, we iterate through each element in the input list. For each element, we checks if it appears only once in the list by iterating through the list again. If an element is found to be repeating, we set the flag *isRepeating* to *true*. If an element is found to be non-repeating, the method returns that element.

Below is the implementation of the above idea:

```
Integer findFirstNonRepeating(List<Integer> list) {
for (int i = 0; i < list.size(); i++) {
int current = list.get(i);
boolean isRepeating = false;
for (int j = 0; j < list.size(); j++) {
if (i != j && current == list.get(j)) {
isRepeating = true;
break;
}
}
if (!isRepeating) {
return current;
}
}
return null;
}
```

Let’s walk through an example list:

`[1, 2, 3, 2, 1, 4, 5, 4]`

During the first iteration, the inner loop scans through the entire list to look for any other occurrence of element *1*. It finds another occurrence of element *1* at index *4*. Since element *1* appears again elsewhere in the list, it’s considered repeating. The process is repeated for element *2*. In the third iteration, it doesn’t find any other occurrence of element *3* in the list. Hence, it’s identified as the first non-repeating element, and the method returns *3*.

### 3.2. Complexity Analysis

Let n be the size of the input list. The outer loop iterates through the list once, resulting in O(n) iterations. The inner loop also iterates through the list once for each outer loop iteration, resulting in O(n) iterations for each outer loop iteration. Therefore, the overall time complexity is O(n^2). The approach uses a constant amount of extra space, regardless of the size of the input list. Hence, the space complexity is O(1).

**This method provides a straightforward solution to find the first non-repeating element. However, it has a time complexity of O(n^2), making it inefficient for large lists.**

## 4. Using *indexOf()* and *lastIndexOf()*

The *indexOf()* method retrieves the index of the first occurrence of an element, while *lastIndexOf()* returns the index of the last occurrence. By comparing these indices for each element in the list, we can identify elements that appear only once.

### 4.1. Implementation

In the iteration, we check if each element’s first occurrence index isn’t equal to its last occurrence index. If they aren’t equal, it means the element appears more than once in the list. If an element is found with the same first and last occurrence indices, the method returns that element as the first non-repeating element:

```
Integer findFirstNonRepeatedElement(List<Integer> list) {
for (int i = 0; i < list.size(); i++) {
if (list.indexOf(list.get(i)) == list.lastIndexOf(list.get(i))) {
return list.get(i);
}
}
return null;
}
```

Let’s walk through the provided example list:

`[1, 2, 3, 2, 1, 4, 5, 4]`

During the initial iteration, both *indexOf(1)* and *lastIndexOf(1)Â *return *0* and *4*. They aren’tÂ equal. This indicates that element *1* is a repeating element. This process is repeated for subsequent element *2*. However, when examining element *3*, both *indexOf(3)* and *lastIndexOf(3) *return *2*. This equality implies that element *3* is the first non-repeating element. Therefore, the method returns *3* as the result.

### 4.2. Complexity Analysis

Let n be the size of the input list. The method iterates through the list once. **For each element, it calls both indexOf() and lastIndexOf(), which may iterate through the list to find the indices.** Therefore, the overall time complexity is O(n^2). This approach uses a constant amount of extra space. Hence, the space complexity is O(1).

While this approach provides a concise solution, it’s inefficient due to its quadratic time complexity (O(n^2)). **For large lists, especially with repeated calls to indexOf() and lastIndexOf(), this method may be significantly slower compared to other approaches.**

## 5. Using *HashMap*

In another way, we can use a *HashMap* to count occurrences of each element and then find the first non-repeating element. This approach is more efficient than the simple *for* loop method.

### 5.1. Implementation

**In this method, we iterate through the input list to count the occurrences of each element and store them in the HashMap.** After counting the occurrences, we iterate through the list again and check if the count of each element is equal to

*1*. If the count is equal to

*1*for any element, it returns that element as the first non-repeating element. If no non-repeating element is found after iterating through the entire list, it returns

*-1*.

Below is the implementation of the above idea:

```
Integer findFirstNonRepeating(List<Integer> list) {
Map<Integer, Integer> counts = new HashMap<>();
for (int num : list) {
counts.put(num, counts.getOrDefault(num, 0) + 1);
}
for (int num : list) {
if (counts.get(num) == 1) {
return num;
}
}
return null;
}
```

Let’s walk through the provided example list:

`[1, 2, 3, 2, 1, 4, 5, 4]`

The *counts* after the first iteration will be:

`{1=2, 2=2, 3=1, 4=2, 5=1}`

When iterating through the list, *1* and *2* have counts greater than *1*, so they aren’t non-repeating. Element *3* has a count of *1*, so it’s the first non-repeating element.

### 5.2. Complexity Analysis

Let n be the size of the input list. Counting occurrences of each element in the list takes O(n) time. Iterating through the list to find the first non-repeating element also takes O(n) time. Therefore, the **overall time complexity is O(n)**. This approach uses additional space proportional to the number of unique elements in the input list. **In the worst case, where all elements are unique, the space complexity is O(n).Â **

**This method provides an efficient solution to finding the first non-repeating element in a list for a wide range of input data.** It utilizes a *HashMap* to keep track of element occurrences, which significantly improves the performance compared to the traditional *for* loop approach.

## 6. Using Array as Frequency Counter

This method uses an array as a frequency counter to count occurrences of each element and find the first non-repeating element.

### 6.1. Implementation

At first, we initialize an array *frequency* of size *maxElement + 1*, where *maxElement* is the maximum element in the list. We iterate through the list, and for each element *num*, increment *frequency[num]*. This step ensures that *frequency[i]* stores the count of occurrences of the element* i*.

Next, we iterate through the list again. For each element *num*, we check if *frequency[num]* is equal to *1*. If *frequency[num]* is *1*, we return *num* as it’s the first non-repeating element:

```
Integer findFirstNonRepeating(List<Integer> list) {
int maxElement = Collections.max(list);
int[] frequency = new int[maxElement + 1];
for (int num : list) {
frequency[num]++;
}
for (int num : list) {
if (frequency[num] == 1) {
return num;
}
}
return null;
}
```

Let’s walk through the provided example list:

`[1, 2, 3, 2, 1, 4, 5, 4]`

We initialize the frequency array with all elements set to zero:

`[0, 0, 0, 0, 0, 0]`

We iterate through the list:

```
Increment frequency[1] to 2.
Increment frequency[2] to 2.
Increment frequency[3] to 1.
Increment frequency[4] to 2.
Increment frequency[5] to 1.
```

Next, we iterate through the list again, for* frequency[1]* and *frequency[2]* the value is *2*, so it’s not non-repeating. For *frequency[3]*, the value is equal to *1*, so the method returns *3*.

### 6.2. Complexity Analysis

Let n be the size of the input list. We iterate through the list twice, but each iteration provides a time complexity of O(n). This approach is more memory-efficient than the *HashMap* approach, with a space complexity of O(maxElement).

This approach is particularly efficient when the range of elements in the list is small because it avoids the overhead of hashing and provides a more straightforward implementation. **However, if the input list contains negative numbers or zero, the frequency array must cover the entire range of possible elements, including negative numbers if applicable.**

## 7. Summary

Here’s a comparison table for the different implementations:

Method | Time Complexity | Space Complexity | Efficiency | Suitable for Large Lists |
---|---|---|---|---|

Using for Loop |
O(n^2) | O(1) | Low | No |

Using indexOf() |
O(n^2) | O(1) | Low | No |

Using HashMap |
O(n) | O(n) | High | Yes |

Using Array Counter | O(n) | O(maxElement) | High | No |

## 8. Conclusion

In this article, we learned a few approaches to finding the first non-repeating element in a list, each with its advantages and considerations. While each method offers its advantages and considerations, the HashMap approach stands out for its efficiency in identifying the first non-repeating element. By leveraging HashMaps, we can achieve optimal performance.

As always, the source code for the examples is availableÂ over on GitHub.