LeetCode 1748 - Sum of Unique Elements

LeetCode Problem 1748

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem gives us an integer array nums and asks us to compute the sum of all elements that appear exactly once in the array.

An element is considered unique only if its frequency is exactly one. If a value appears two or more times, it must not contribute to the final sum at all.

For example, in the array [1,2,3,2], the number 2 appears twice, so it is not unique. The numbers 1 and 3 each appear once, so the answer becomes 1 + 3 = 4.

The input is a list of integers where:

• nums.length ranges from 1 to 100
• nums[i] ranges from 1 to 100

These constraints are very small. Even a quadratic solution would technically pass comfortably. However, the goal is still to design a clean and efficient approach that scales naturally and demonstrates good algorithmic thinking.

The key observation is that we need frequency information. We cannot determine whether a number is unique by looking at it once in isolation. We must know how many times every value appears in the array.

Some important edge cases are worth considering early:

• Arrays where every element is duplicated, such as [1,1,2,2], should return 0
• Arrays where every element is unique, such as [1,2,3], should return the sum of all values
• Arrays containing only one element, such as [7], should return that element itself
• Arrays with repeated values scattered throughout the input should still count frequencies correctly

The problem guarantees that the array is non-empty and all values are positive integers, so we never need to handle invalid or missing input.

Approaches

Brute Force Approach

A straightforward solution is to examine each element individually and count how many times it appears in the array.

For every number nums[i], we can scan the entire array and count its occurrences. If the count equals one, we add it to the answer.

This approach works because it directly follows the problem definition. We explicitly determine whether each element appears exactly once.

However, this method is inefficient because for every element we perform another full traversal of the array. If the array has n elements, the total work becomes O(n²).

Even though the constraints are small enough that this would pass, it is not the best design.

Optimal Approach

The better solution is to count frequencies first using a hash map.

We make one pass through the array and record how many times each number appears. Then we make another pass through the frequency map and sum only the values whose frequency is exactly one.

The important insight is that frequency counting converts repeated expensive scans into constant-time lookups.

A hash map is ideal here because:

• It stores counts efficiently
• Insertions and lookups are average O(1)
• It naturally handles repeated values

This reduces the total time complexity from quadratic to linear.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	For each element, scan the entire array again to count occurrences
Optimal	O(n)	O(n)	Use a hash map to store frequencies, then sum values appearing once

Algorithm Walkthrough

1. Create an empty hash map called frequency.

This map will store each number as the key and the number of times it appears as the value. 2. Traverse the array once.

For every number in nums, increment its count in the hash map.

After this pass, the map contains complete frequency information for all elements. 3. Initialize a variable called unique_sum to 0.

This variable will accumulate the final answer. 4. Traverse the frequency map.

For each (number, count) pair:

• If count == 1, add the number to unique_sum
• Otherwise, ignore it because it is not unique

5. Return unique_sum.

At this point, the sum contains exactly the values that appeared once in the array.

Why it works

The algorithm works because the frequency map stores the exact number of occurrences for every distinct element.

An element contributes to the answer if and only if its frequency equals one. Since every number is counted correctly during the first traversal, the second traversal can accurately identify all unique elements.

No element is missed, and no duplicated element is incorrectly included.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        frequency = Counter(nums)

        unique_sum = 0

        for number, count in frequency.items():
            if count == 1:
                unique_sum += number

        return unique_sum

The implementation uses Python's Counter class from the collections module to simplify frequency counting.

The line frequency = Counter(nums) automatically creates a hash map where each key is a number from the array and each value is its occurrence count.

Next, the variable unique_sum is initialized to zero. We iterate through every (number, count) pair in the frequency map. Whenever the count equals one, we add the number to the running total.

Finally, we return the accumulated sum.

This implementation directly mirrors the algorithm described earlier and keeps the code concise and readable.

Go Solution

func sumOfUnique(nums []int) int {
	frequency := make(map[int]int)

	for _, num := range nums {
		frequency[num]++
	}

	uniqueSum := 0

	for num, count := range frequency {
		if count == 1 {
			uniqueSum += num
		}
	}

	return uniqueSum
}

The Go solution follows the same logic as the Python version but uses Go's built-in map type for frequency counting.

The statement make(map[int]int) creates a hash map from integers to integers. During iteration, each number's count is incremented.

Go does not have a built-in Counter equivalent like Python, so frequency counting is performed manually.

There are no special concerns about integer overflow because the constraints are very small. The maximum possible sum is at most 1 + 2 + ... + 100 = 5050, which easily fits inside Go's int type.

Worked Examples

Example 1

Input:

nums = [1,2,3,2]

Frequency Counting Phase

Step	Current Number	Frequency Map
1	1	{1: 1}
2	2	{1: 1, 2: 1}
3	3	{1: 1, 2: 1, 3: 1}
4	2	{1: 1, 2: 2, 3: 1}

Summation Phase

Number	Count	Add to Sum?	Running Sum
1	1	Yes	1
2	2	No	1
3	1	Yes	4

Final answer:

4

Example 2

Input:

nums = [1,1,1,1,1]

Frequency Counting Phase

Step	Current Number	Frequency Map
1	1	{1: 1}
2	1	{1: 2}
3	1	{1: 3}
4	1	{1: 4}
5	1	{1: 5}

Summation Phase

Number	Count	Add to Sum?	Running Sum
1	5	No	0

Final answer:

0

Example 3

Input:

nums = [1,2,3,4,5]

Frequency Counting Phase

Step	Current Number	Frequency Map
1	1	{1: 1}
2	2	{1: 1, 2: 1}
3	3	{1: 1, 2: 1, 3: 1}
4	4	{1: 1, 2: 1, 3: 1, 4: 1}
5	5	{1: 1, 2: 1, 3: 1, 4: 1, 5: 1}

Summation Phase

Number	Count	Add to Sum?	Running Sum
1	1	Yes	1
2	1	Yes	3
3	1	Yes	6
4	1	Yes	10
5	1	Yes	15

Final answer:

15

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count frequencies and one pass to compute the sum
Space	O(n)	The hash map may store every distinct element

The algorithm processes each element a constant number of times. Hash map operations are average O(1), so the total running time grows linearly with the input size.

The extra space comes from storing frequency counts. In the worst case, every element is distinct, so the hash map contains n entries.

Test Cases

from typing import List
from collections import Counter

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        frequency = Counter(nums)

        unique_sum = 0

        for number, count in frequency.items():
            if count == 1:
                unique_sum += number

        return unique_sum

solution = Solution()

assert solution.sumOfUnique([1, 2, 3, 2]) == 4  # basic mixed duplicates
assert solution.sumOfUnique([1, 1, 1, 1, 1]) == 0  # all elements duplicated
assert solution.sumOfUnique([1, 2, 3, 4, 5]) == 15  # all unique elements
assert solution.sumOfUnique([7]) == 7  # single element array
assert solution.sumOfUnique([2, 2]) == 0  # smallest duplicated case
assert solution.sumOfUnique([5, 6, 5, 7, 8, 8]) == 13  # multiple duplicate groups
assert solution.sumOfUnique([100]) == 100  # maximum value boundary
assert solution.sumOfUnique([1, 100, 1, 50]) == 150  # mixed small and large values
assert solution.sumOfUnique([9, 9, 8, 7, 7, 6]) == 14  # only some values unique
assert solution.sumOfUnique([3, 3, 3, 2, 2, 1]) == 1  # exactly one unique value

Test Case Summary

Test	Why
[1,2,3,2]	Verifies standard mixed input
[1,1,1,1,1]	Ensures duplicated values are excluded
[1,2,3,4,5]	Confirms all unique elements are summed
[7]	Tests smallest possible array
[2,2]	Tests smallest duplicated array
[5,6,5,7,8,8]	Verifies multiple duplicate groups
[100]	Tests upper bound element value
[1,100,1,50]	Tests mixed frequency distribution
[9,9,8,7,7,6]	Confirms only unique elements contribute
[3,3,3,2,2,1]	Tests exactly one unique element

Edge Cases

One important edge case is when every element appears multiple times. For example, [1,1,2,2] contains no unique values. A buggy implementation might accidentally include duplicated numbers if it only checks whether a number has been seen before. The frequency-map approach handles this correctly because only numbers with count exactly equal to one are added to the sum.

Another important case is when every element is unique, such as [1,2,3,4]. In this scenario, the algorithm should return the sum of the entire array. Since each frequency count becomes one, every number is included naturally during the summation phase.

A third edge case is a single-element array like [42]. Since the only element appears exactly once, it must be returned directly. The implementation handles this automatically because the frequency map stores {42: 1}, and the summation phase adds it to the answer.

A subtle case involves duplicated elements appearing far apart in the array, such as [1,2,3,1]. A naive implementation that only compares neighboring values would fail here. The hash map approach avoids this problem entirely because it tracks total frequencies globally across the whole array.