Find All Non-Repeating Elements in an Array

7
1

Given an integer array nums, return all elements that appear exactly once. The elements can be returned in any order.

Example 1

Input: nums = [4, 2 , 4 , 4 , 5]

Output: [2 , 5]

Explanation: 2 and 5 appear once each, while 4 appear twice.

Example 2

Input: nums = [5, 5, 8, 8, 8]

Output: []

Explanation: Every number appears more than once, so the result is empty.

Brute Force Approach

A number belongs in the answer only if it appears once in the entire array. To check this directly, pick an element and compare its value with every element in the array, including itself. Each match adds one to its total count.

If the final count is exactly one, keep that number. If the count is greater than one, skip it. Repeat this check for every position in the array.

This method is simple, but it counts the same values again when their other copies are reached. Even numbers that appear once need a full scan to confirm that no other copy exists.

Algorithm

  • Start with an empty result list.

  • Pick an element from the array and start its count at zero.

  • Scan the entire array and count every value equal to the selected element.

  • If the count is exactly one, add the selected element to the result.

  • Repeat for every element and return the result list.

Dry Run

Find all non repeating elements in an array - brute

Find all non repeating elements in an array - brute

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns every number that appears exactly once.
vector<int> findNonRepeatingElements(vector<int>& nums) {
vector<int> result;
// Check the total count of each selected value.
for (int value : nums) {
int count = 0;
// Include every matching position, including the current one.
for (int current : nums) {
if (current == value) {
count++;
}
}
// Keep the value only when no other copy exists.
if (count == 1) {
result.push_back(value);
}
}
return result;
}
};
// Driver code
int main() {
vector<int> nums = {4, -2, 7, 4, 9, 7};
// Create an instance of Solution.
Solution sol;
vector<int> result = sol.findNonRepeatingElements(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²) because each of the N elements is compared with every element in the array.

Space Complexity: O(1) extra space, excluding the result list. The result can contain up to N elements, so its space requirement is O(N) in the worst case.

Optimal Approach

The repeated scans happen because the brute force method does not remember the counts it has already found. A hash map can store each different number together with how many times it appears. This count is called its frequency.

Go through the array once to build these frequencies. When a number appears for the first time, its count becomes one. Every later appearance increases its existing count.

After counting the entire array, go through the numbers again and keep only those whose final frequency is one. Counting must finish before choosing the answer, because a number seen once so far might appear again later. This second scan also keeps the selected numbers in their original order, although the problem allows any output order.

Algorithm

  • Create an empty hash map to store the frequency of each number.

  • Traverse the array and increase the stored frequency of each number by one.

  • Create an empty result list.

  • Traverse the original array again and check each number’s final frequency.

  • Add a number to the result only if its frequency is exactly one.

  • Return the result list.

Dry Run

Find all non repeating elements in an array - optimal

Find all non repeating elements in an array - optimal

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns every number that appears exactly once.
vector<int> findNonRepeatingElements(vector<int>& nums) {
unordered_map<int, int> frequency;
// Count all appearances before selecting any answer.
for (int value : nums) {
frequency[value]++;
}
vector<int> result;
// Scan the original array to keep its order in the result.
for (int value : nums) {
// Only a final frequency of one means non-repeating.
if (frequency[value] == 1) {
result.push_back(value);
}
}
return result;
}
};
// Driver code
int main() {
vector<int> nums = {4, -2, 7, 4, 9, 7};
// Create an instance of Solution.
Solution sol;
vector<int> result = sol.findNonRepeatingElements(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. The array is scanned twice, and each hash-map update or lookup takes expected O(1) time.

Space Complexity: O(N) extra space in the worst case, since the hash map may store a count for every element. The result list can also contain up to N elements.

Interview follow-up Questions

Not in the general case. XORing the entire array produces one value, which does not reveal a list of multiple non-repeating numbers. The common XOR shortcut works when exactly one number appears once and every other number appears twice, which is not guaranteed here.

ArraysHashingTCS NQT

Read Similar Blogs

Comments0