Given an integer array nums, return each number that appears more than once. Include each repeating number only once. The answer can be in any order.
Example 1
Input: nums = [2, 6, 2, 4, 6, 2]
Output: [2, 6]
Explanation: 2 appears three times and 6 appears twice, so both are included once.
Example 2
Input: nums = [5, -1, 8, 0]
Output: []
Explanation: Every number appears once, so there are no repeating elements.
Brute Force Approach
A number repeats if another position contains the same value. The direct way to check this is to pick a number and search the positions after it for a match. Finding even one match is enough to include that number in the answer.
However, a number might appear three or more times. Checking every copy in the same way could add that number to the answer more than once.
To prevent this, first check whether the current value has already appeared earlier in the array. If it has, skip this copy because its first appearance has already been checked. Otherwise, search to the right and add the value if a match is found. This keeps each repeating number in the answer only once.
Algorithm
Start with an empty result list.
Visit each position from left to right.
Check whether the current value appears at an earlier position. If it does, skip the current position.
Otherwise, search the positions to its right for the same value.
If a match is found, add the value to the result and stop searching for that value.
Return the result after checking all positions.
Dry Run
Find all repeating elements in an array - Brute
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Returns each repeating number exactly once. vector<int> findRepeatingElements(vector<int>& nums) { vector<int> result; int n = nums.size(); for (int index = 0; index < n; index++) { bool alreadySeen = false; // Check whether an earlier copy has already been handled. for (int previous = 0; previous < index; previous++) { if (nums[previous] == nums[index]) { alreadySeen = true; break; } } if (alreadySeen) { continue; } // Search to the right for another copy. for (int nextIndex = index + 1; nextIndex < n; nextIndex++) { if (nums[nextIndex] == nums[index]) { result.push_back(nums[index]); // One match is enough to confirm repetition. break; } } } return result; }};// Driver codeint main() { vector<int> nums = {2, 6, 2, 4, 6, 2}; // Create an instance of Solution. Solution sol; vector<int> result = sol.findRepeatingElements(nums); // Print the result as a list. cout << "["; for (int index = 0; index < result.size(); index++) { if (index > 0) { cout << ", "; } cout << result[index]; } cout << "]\n"; return 0;}Complexity Analysis
Time Complexity: O(N²) in the worst case. For each position, checking earlier values and searching later values can together take O(N) time.
Space Complexity: O(1) extra space, excluding the result list. The result can require O(N) space in the worst case.
Optimal Approach
Instead of searching for matching copies, keep a count for each number. A hash map stores a number together with how many times it has appeared. This count is called its frequency.
Read the array from left to right. The first time a number appears, its count becomes one. Each later appearance increases that same count. Once the array has been read, the map contains the total count of every different number.
Now check the map entries. A count greater than one means the number repeats, so include it in the answer. Each different number has only one entry in the map, which means it is added only once, even if it appears many times.
Algorithm
Create an empty hash map to store the frequency of each number.
Traverse the array and increase the count of each number by one.
Create an empty result list.
Visit each entry in the frequency map.
If its count is greater than one, add that number to the result.
Return the result list.
Dry Run
Find all repeating elements in an array - Optimal
Solution
#include<bits/stdc++.h>using namespace std;class Solution {public: // Returns each repeating number exactly once. vector<int> findRepeatingElements(vector<int>& nums) { unordered_map<int, int> frequency; // Record the total number of appearances of each value. for (int value : nums) { frequency[value]++; } vector<int> result; // Each map entry represents one different number. for (const auto& entry : frequency) { // A count above one means the number repeats. if (entry.second > 1) { result.push_back(entry.first); } } return result; }};// Driver codeint main() { vector<int> nums = {2, 6, 2, 4, 6, 2}; // Create an instance of Solution. Solution sol; vector<int> result = sol.findRepeatingElements(nums); // Print the result as a list. cout << "["; for (int index = 0; index < result.size(); index++) { if (index > 0) { cout << ", "; } cout << result[index]; } cout << "]\n"; return 0;}Complexity Analysis
Time Complexity: O(N) expected time. Counting takes one pass through the array, and checking the map visits at most N entries. Hash-map updates take expected O(1) time.
Space Complexity: O(N) extra space in the worst case for the frequency map. The result list can also require O(N) space.
Interview follow-up Questions
Yes. Comparisons, sorting, and hash-map keys all support negative numbers and zero. The values do not need to fall within the array’s index range.
Be the first to add a comment.