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.