Sum of Unique Elements - Solution & Explanation

Problem Overview: You receive an integer array nums. The task is to compute the sum of elements that appear exactly once in the array. Any number that appears more than once must be ignored. The challenge is efficiently identifying which values have frequency 1.

Approach 1: Frequency Count and Sum (O(n) time, O(n) space)

This approach uses a frequency map to count how many times each number appears. Iterate through the array once and store counts in a hash table. Then iterate over the frequency map and add values whose count equals 1. Hash table lookup and insertion both run in constant time on average, so the entire operation is linear. This method is straightforward and widely used in problems involving element frequency tracking. It relies on a hash table for constant-time updates and works well for unsorted arrays.

The key insight is separating counting from summation. Instead of trying to determine uniqueness while iterating, first build a complete frequency distribution. Once you know exact counts, computing the result becomes trivial. This pattern appears frequently in problems involving duplicates, histograms, or occurrence tracking.

Approach 2: Single Pass with Multiple Sets (O(n) time, O(n) space)

This approach tracks numbers using two sets during a single traversal. Maintain a unique set for numbers seen exactly once and a duplicates set for numbers seen more than once. As you iterate through the array, check whether the number has been seen before. If it appears for the first time, insert it into unique. If it appears again, remove it from unique and add it to duplicates. At the end, sum all values remaining in unique.

The advantage is that counting and filtering happen simultaneously in one pass. Set membership checks and updates are constant time on average because they use hashing internally. This technique is common when you need to dynamically maintain "seen once" vs "seen multiple times" elements. It still uses hashing internally, making it conceptually similar to the counting approach but slightly more dynamic.

Both strategies operate in linear time and rely on efficient lookups provided by a hash table. Since the input is simply an array, the algorithm focuses on tracking frequencies rather than modifying structure or order. Problems involving frequency counting are often categorized under counting techniques.

Recommended for interviews: The frequency counting approach is usually the expected solution. It is simple, easy to reason about, and clearly demonstrates understanding of hash maps and counting patterns. The set-based single-pass method is equally efficient but slightly less common. Interviewers typically want to see the frequency map solution first because it generalizes well to many duplicate-handling problems.