Sum of Unique Elements — Editorial

Opening the reading…

Intuitionwhy uniqueness is a final frequency property

An element is unique only after you know how many times it appears in the entire array. Seeing a value once while scanning is not enough: it may appear again later. The safe first step is therefore to record one frequency for each value, so every candidate can be judged against the complete array rather than against the prefix seen so far.

Once the counts are complete, the rule becomes direct. A value with count 1 contributes its value to the sum; a value with count 0 or any count greater than 1 contributes nothing. The map stores each distinct value and its count, so the second pass examines each candidate exactly once and applies the definition without repeated searching.

Approachtwo passes keep counting separate from deciding

Create a frequency map from integer value to occurrence count, because the final answer depends on how often each value appears.

Scan nums once and increment freq[x] for every x, so repeated values accumulate their complete counts instead of being mistaken for unique values.

Set sum to zero before examining the map, because no value should contribute until its full frequency is known.

Iterate through every value-count pair in the map and add the value only when its count equals 1; using equality is essential because values appearing twice or more are not unique.

Return sum after the map pass, because every possible contributor has then been considered exactly once and no later correction is needed.

Complexitythe map stores one entry per distinct value

MEASURE	BOUND	WHY
Time	O(n)	The first pass performs one average-constant-time hash update per array element. The second pass visits each distinct value once, and there can be at most n of them, so the two pass costs add to O(n).
Space	O(n) extra	The returned value is a scalar, so there is no output collection to count. The frequency map holds one entry per distinct value; in the worst shape, every array element is different and the map has n entries.

Here n is the length of nums. The number of distinct values is at most n.

Annotated solutionC++ · two-pass hash map · count first, filter second

CPPBuild the complete frequency map, then sum the entries whose count is one.

#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) {
            freq[x]++;
        }

        int sum = 0;
        for (auto& p : freq) {
            if (p.second == 1) {
                sum += p.first;
            }
        }

        return sum;
    }
};

The placement of the two loops is the central detail. If you add a value when its count first becomes one, a later duplicate cannot reliably undo that contribution without extra bookkeeping. Waiting until counting finishes makes p.second == 1 a final fact, so the sum line needs no special case for a second or third occurrence.

The bounded-array alternativea fixed frequency table trades generality for constant extra space

The input values are restricted to 1 through 100, so a hash map is not the only reasonable choice. A frequency array with 101 slots can represent every possible value directly. This is an optimisation under these bounds, not a generally better hashing technique: it removes hashing overhead and uses O(1) extra space, but it must be resized or replaced if the allowed value range changes.

CPPUse one array slot for each allowed value, then scan the complete range.

#include <vector>
using namespace std;

class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        vector<int> freq(101, 0);
        for (int x : nums) {
            freq[x]++;
        }

        int sum = 0;
        for (int x = 1; x <= 100; ++x) {
            if (freq[x] == 1) {
                sum += x;
            }
        }

        return sum;
    }
};

The array version still has the same two logical passes: first establish final counts, then select count-one values. Its time is O(n + 100), which is O(n) for this fixed range, and its extra space is O(1) because the 101 counters do not grow with n. The hash-map version is preferable when the value range is unknown or much larger than the array.