Given an array of integers, find the first element that appears exactly once. Among all non-repeating elements, return the one with the smallest index. If every element repeats, return -1.
Example 1
Input: arr = [9, 4, 9, 6, 7, 4]
Output: 6
Explanation: The values 9 and 4 repeat. The values 6 and 7 appear once. Since 6 appears before 7, the answer is 6.
Example 2
Input: arr = [2, 2, 3, 3]
Output: -1
Explanation: Every value appears more than once. No non-repeating element exists, so the answer is -1.
Brute Force Approach
The goal is to find the first element that appears exactly once in the array. So the direct idea is to find out the elements with single occurrence and among them the first element is the required answer. If every element appears more than once, no non-repeating element exists, and the answer is -1.
Algorithm
If the array is empty, no non-repeating element exists, so return
-1.Start checking the elements from left and for every element count how many times that element appears.
If an element with an occurrence count of
1is found, this is going to be the first non-repeating element.If no non-repeating element has been found, return -1.
Dry Run
Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds first value with frequency one using repeated scans. int firstNonRepeating(vector<int>& arr) { // An empty array has no non-repeating value. if (arr.empty()) { return -1; } // Check each value in original order. for (int current = 0; current < arr.size(); current++) { int count = 0; // Count every occurrence of the current value. for (int value : arr) { // Increase the count after finding an equal value. if (value == arr[current]) { count++; } } // Return the first value that appears once. if (count == 1) { return arr[current]; } } // Return -1 when no non-repeating value was found. return -1; }};// Driver code startsint main() { vector<int> arr = {9, 4, 9, 6, 7, 4}; Solution solution; cout << solution.firstNonRepeating(arr) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N²), where N is the number of elements in the array. For every element, the entire array is traversed.
Space Complexity: O(1) — because only loop positions and one occurrence count are stored.
Better Approach
The goal is to find the element that appears only once and has the earliest position in the original array. By grouping equal values together using sorting, every unique element can be identified easily. Among all such unique elements, the one with the smallest original position is the first non-repeating element.
Algorithm
If the array is empty return
-1.Store every element along with its index and sort the pairs by value to make equal values adjacent.
Start processing one group at a time. The pointer
leftmarks the start of the current group, whilerightkeeps moving forward until a different value is encountered.If a group contains only one element, check its original index. If it is smaller then update answer.
After a group has been processed,
leftmoves to the position ofrightand continue the process.If every group contains multiple elements return
-1. Otherwise, return the number having smallest recorded index.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds first non-repeating value after sorting value-position pairs. int firstNonRepeating(vector<int>& arr) { // An empty array has no non-repeating value. if (arr.empty()) { return -1; } vector<pair<int, int>> indexedValues; // Store every value with the original position. for (int index = 0; index < arr.size(); index++) { indexedValues.push_back({arr[index], index}); } // Default pair sorting uses value first and position second. sort(indexedValues.begin(), indexedValues.end()); int firstIndex = -1; int left = 0; // Process one equal-value group during each pass. while (left < indexedValues.size()) { int right = left + 1; // Move to the first pair with a different value. while ( right < indexedValues.size() && indexedValues[right].first == indexedValues[left].first ) { right++; } // A group of size one contains a non-repeating value. if (right - left == 1) { int candidateIndex = indexedValues[left].second; // Save the earliest original position found so far. if (firstIndex == -1 || candidateIndex < firstIndex) { firstIndex = candidateIndex; } } left = right; } // Return -1 when no non-repeating value was found. if (firstIndex == -1) { return -1; } return arr[firstIndex]; }};// Driver code startsint main() { vector<int> arr = {9, 4, 9, 6, 7, 4}; Solution solution; cout << solution.firstNonRepeating(arr) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N log(N)), where N is the number of elements in the array. Sorting dominates the running time, while the remaining work only requires a single pass through the sorted pairs.
Space Complexity: O(N), where N is the number of elements in the array. An extra array is used to store each value along with its original position.
Optimal Approach
The key idea is to identify all the elements that appear exactly once in the array. So the frequencies of all the elements can be calculated using hash-map and then the array is checked again in its original order. The first element with a frequency of 1 is the first non-repeating element.
Algorithm
If the array is empty return
-1.The frequency of every element can be counted using a hash map and then start traversing the array from left.
Whenever an element with a frequency of
1is encountered, that is the first non-repeating element, so return it.Otherwise, continue the traversal and return
-1if ended up without finding a non-repeating element.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the first non-repeating value using stored frequencies. int firstNonRepeating(vector<int>& arr) { // An empty array has no non-repeating value. if (arr.empty()) { return -1; } unordered_map<int, int> frequency; // Count every array value. for (int value : arr) { frequency[value]++; } // Read the original order to find the earliest unique value. for (int value : arr) { // A frequency of one marks a non-repeating value. if (frequency[value] == 1) { return value; } } // Return -1 when no non-repeating value was found. return -1; }};// Driver code startsint main() { vector<int> arr = {9, 4, 9, 6, 7, 4}; Solution solution; cout << solution.firstNonRepeating(arr) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N) on average, where N is the number of elements in the array. One traversal stores the frequencies, and another checks for the first non-repeating element.
Space Complexity: O(K), where K is the number of distinct values stored in the hash map.
Be the first to add a comment.