Sum of Unique Elements

easy array hash map counting

Problem

An element is unique if it appears exactly once in nums. Return the sum of all the unique elements.

Inputnums = [1,2,3,2]

Output4

1 and 3 appear once; 2 repeats. 1 + 3 = 4.

nums

def sum_of_unique(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    total = 0
    for x, c in count.items():
        if c == 1:
            total += x
    return total

function sumOfUnique(nums) {
  const count = new Map();
  for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
  let total = 0;
  for (const [x, c] of count) {
    if (c === 1) total += x;
  }
  return total;
}

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

int sumOfUnique(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int x : nums) count[x]++;
    int total = 0;
    for (auto& [x, c] : count)
        if (c == 1) total += x;
    return total;
}

Explanation

A value counts toward the answer only when it appears exactly once. So we first need to know the frequency of every value, which is a perfect job for a hash map from value to count.

In the first pass we walk the array and bump count[x] for each element. After this pass the map holds how many times each distinct value occurred.

In the second pass we iterate over the map's entries and add a value to total only when its count is 1. Values that repeated are skipped entirely.

Both passes are linear and the map operations are O(1) on average, so the whole solution runs in O(n) time and O(n) extra space for the map.

Example: [1,2,3,2]. Counts become {1:1, 2:2, 3:1}. Only 1 and 3 have count 1, so the answer is 1 + 3 = 4.

Time: O(n) Space: O(n)