Given an integer array arr[], find the first value that appears more than once.
Return -1 when no repeating value exists.
Example 1
Input: arr = [2, 1, 3, 4, 3, 4]
Output: 3
Explanation: The values 3 and 4 both appear multiple times. The first 3 is at index 2, while the first 4 is at index 3. Therefore, 3 is the first repeating element.
Example 2
Input: arr = [1, 2, 3, 4]
Output: -1
Explanation: Every value appears exactly once, so the answer is -1.
Brute Force Approach
The simplest idea is to compare each element with all the elements that come after it. If the same value is found again, that element is the first repeating element in the array.
Algorithm
Start from the first element and move from left to right.
The current element can be compared with every element that comes after it.
If an equal element is found, the current element is returned immediately.
If no repeating element is found after checking all elements, return
-1.
Dry Run
brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the first repeating value by checking every later value. int firstRepeating(vector<int>& arr) { // Fewer than two values cannot contain a repeat. if (arr.size() < 2) { return -1; } // Check possible first repeating values from left to right. for (int current = 0; current < arr.size(); current++) { // Search for the same value at a later position. for (int later = current + 1; later < arr.size(); later++) { // Return the earliest value after finding a later copy. if (arr[current] == arr[later]) { return arr[current]; } } } // Return -1 when no repeating value was found. return -1; }};// Driver code startsint main() { vector<int> arr = {2, 1, 3, 4, 3, 4}; Solution solution; cout << solution.firstRepeating(arr) << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N²), where N is the number of elements in the array. In the worst case, every value may be compared with all later values.
Space Complexity: O(1) — no extra space is used.
Better Approach
The main idea is to identify all the values that appear more than once and then determine which one of those values occurs first in the original array. Instead of checking every pair of elements, repeated values can be found more efficiently using sorting, and the earliest occurrence among them gives the first repeating element.
Algorithm
Store every element along with its original index as a
(value, index)pair and sort all pairs by their value.A variable is used to store the smallest index among all repeated values found so far.
Then the sorted list is traversed from left to right and compare each pair with the previous one.
Whenever two adjacent pairs have the same value, use the smaller original index as the candidate and update the stored index if the candidate is smaller.
After the scan, return
-1if no repeated value was found.Otherwise, return the element corresponding to the smallest recorded original index.
Dry Run
Better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Finds the first repeating value after sorting value-position pairs. int firstRepeating(vector<int>& arr) { // Fewer than two values cannot contain a repeat. if (arr.size() < 2) { 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; // Compare neighboring pairs to find repeated values. for (int current = 1; current < indexedValues.size(); current++) { // Equal neighboring values belong to a repeated group. if (indexedValues[current].first == indexedValues[current - 1].first) { int candidateIndex = min( indexedValues[current].second, indexedValues[current - 1].second ); // Save the earliest original position found so far. if (firstIndex == -1 || candidateIndex < firstIndex) { firstIndex = candidateIndex; } } } // Return -1 when no repeating value was found. if (firstIndex == -1) { return -1; } return arr[firstIndex]; }};// Driver code startsint main() { vector<int> arr = {2, 1, 3, 4, 3, 4}; Solution solution; cout << solution.firstRepeating(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 every value along with its original position.
Optimal Approach
The key idea is to identify repeated values and getting the first occurrence in the original array. Traversing the array from right to left and storing the elements in a hash set makes this possible. Whenever a value is encountered again, it means the current position is an earlier occurrence of that repeated value. As the traversal moves toward the beginning of the array, the last repeated value found automatically becomes the first repeating element.
Algorithm
A hash set can be used to store the values seen during the traversal.
Initialize the answer as
-1.The array should be traversed from the last element toward the first.
Whenever the current value is already present in the hash set, update the answer with that value; otherwise, insert the current value into the hash set.
Return the answer after the traversal is complete.
Dry Run
Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the first repeating element in the array. int firstRepeating(vector<int>& arr) { // Checks whether the array has fewer than two elements. if (arr.size() < 2) { return -1; } unordered_set<int> seenValues; int answer = -1; // Traverses the array from right to left. for (int index = arr.size() - 1; index >= 0; index--) { // Checks whether the current value is already present in set. if (seenValues.find(arr[index]) != seenValues.end()) { answer = arr[index]; } // Inserts current value into the set if not already present. else { seenValues.insert(arr[index]); } } return answer; }};// Driver code startsint main() { vector<int> arr = {2, 1, 3, 4, 3, 4}; Solution solution; cout << solution.firstRepeating(arr) << endl; return 0;}Complexity Analysis
Time Complexity: O(N) on average, where N is the number of elements in the array. Each value is checked and added to the hash set once.
Space Complexity: O(K), where K is the number of distinct values stored in the hash set.
Interview follow-up Questions
unordered_set is implemented using Hash Tables. Average time complexity for insertion and lookup is O(1). So the overall time complexity is O(n). set is implemented using Self-balancing Binary Search Trees. Insertion and lookup take O(log(n)), making the overall time complexity O(nlog(n)).
Be the first to add a comment.