Problem Description

The "Sum of Unique Elements" problem asks you to find the sum of all unique elements in a given integer array nums. An element is considered unique if it appears exactly once in the array. You are to return the sum of all such unique elements.

• You are given an array of integers, nums.
• Your task is to identify all the numbers that appear exactly once in nums.
• Sum up these numbers and return the result.
• Each element in nums can be positive or negative.
• Do not reuse elements; each unique element is counted only once.
• There is always exactly one valid answer for each input.

Thought Process

The core of this problem is to efficiently identify which numbers in the array appear only a single time, then sum them up. The most direct (brute-force) way would be to check, for each element, how many times it appears in the array. If it appears once, add it to the sum. However, this would mean for every element, scanning the entire array, leading to a slow solution.

To optimize, we realize that if we can count the frequency of each number in a single pass, we can then easily find which numbers are unique. This suggests using a data structure that maps each number to its count, such as a hash map (dictionary). This way, we can check uniqueness in constant time per element.

In summary, shift from repeatedly scanning the array (brute-force) to counting all frequencies first, then summing only those with a count of one.

Solution Approach

We can break down the solution into clear steps:

1. Count Frequencies:
   • Use a hash map (dictionary) to store how many times each number appears in nums.
   • Iterate once through nums, updating the count for each number.
2. Sum Unique Elements:
   • Iterate through the hash map.
   • For each number with a count of exactly 1, add it to a running sum.
3. Return the Result:
   • Return the computed sum as the answer.

We use a hash map because it allows us to count each number in O(1) time per insertion and lookup, making the overall process efficient.

Example Walkthrough

Let's walk through an example with nums = [1, 2, 3, 2]:

1. Count Frequencies:
   • Start with an empty hash map.
   • Process 1: map = {1: 1}
   • Process 2: map = {1: 1, 2: 1}
   • Process 3: map = {1: 1, 2: 1, 3: 1}
   • Process 2 again: map = {1: 1, 2: 2, 3: 1}
2. Sum Unique Elements:
   • Check each key:
   • 1 appears once → include in sum
   • 2 appears twice → skip
   • 3 appears once → include in sum
   • Sum = 1 + 3 = 4
3. Return 4

Time and Space Complexity

• Brute-force Approach:
  • For each element, count its occurrences by scanning the array.
  • Time Complexity: O(n²) (for n elements, each scan is O(n))
  • Space Complexity: O(1) (no extra storage beyond variables)
• Optimized Hash Map Approach:
  • Count all frequencies in O(n) time and space.
  • Sum up unique elements in another O(n) pass (over unique keys).
  • Time Complexity: O(n) overall, since both passes are linear.
  • Space Complexity: O(n) for the hash map (in the worst case, all elements are unique).

The optimized solution is much faster and suitable for large arrays.

Summary

To solve the "Sum of Unique Elements" problem, we efficiently count how many times each number appears using a hash map, then sum up only those that appear exactly once. This approach is both simple and powerful, leveraging hash maps for fast lookups and insertions. The key insight is to avoid repeated scanning by counting frequencies up front, resulting in an elegant and efficient linear-time solution.

Code Implementation

class Solution:
    def sumOfUnique(self, nums):
        from collections import Counter
        count = Counter(nums)
        return sum(num for num, freq in count.items() if freq == 1)
      

class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        int sum = 0;
        for (auto& kv : count) {
            if (kv.second == 1) sum += kv.first;
        }
        return sum;
    }
};
      

class Solution {
    public int sumOfUnique(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            if (entry.getValue() == 1) sum += entry.getKey();
        }
        return sum;
    }
}
      

var sumOfUnique = function(nums) {
    const count = {};
    for (const num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    let sum = 0;
    for (const num in count) {
        if (count[num] === 1) sum += Number(num);
    }
    return sum;
};