Problem Description

You are given an integer array nums. Your task is to find all elements that appear exactly once in the array (these are called unique elements) and return their sum.

For example:

• If nums = [1, 2, 3, 2], the unique elements are 1 and 3 (since 2 appears twice), so the sum would be 1 + 3 = 4
• If nums = [1, 1, 1, 1], there are no unique elements (since 1 appears four times), so the sum would be 0
• If nums = [1, 2, 3, 4, 5], all elements are unique, so the sum would be 1 + 2 + 3 + 4 + 5 = 15

The solution uses a Counter to count the frequency of each element in the array. Then it iterates through the counter and sums up only those elements whose count is exactly 1. The Counter(nums) creates a dictionary-like object where keys are the elements and values are their frequencies. The comprehension sum(x for x, v in cnt.items() if v == 1) adds up all elements x where the count v equals 1.

Intuition

To find elements that appear exactly once, we need to know how many times each element appears in the array. This naturally leads us to think about counting frequencies.

The key insight is that we can solve this problem in two steps:

1. Count how many times each element appears
2. Filter and sum only those elements with a count of 1

Why is counting the best approach? Consider the alternatives:

• We could check each element against every other element to see if it's unique, but this would be inefficient with O(n²) time complexity
• We could sort the array and check adjacent elements, but this would take O(n log n) time and be more complex to implement

Using a frequency counter gives us O(n) time complexity - we make one pass to count all elements, then one pass through the unique elements to sum them up. Python's Counter class makes this particularly elegant, as it handles the counting automatically and provides an easy way to iterate through elements with their counts.

The beauty of this solution is its simplicity: once we have the frequency of each element, identifying which ones appear exactly once becomes trivial - we just check if count == 1. Then summing these filtered elements gives us our answer directly.

Solution Approach

The implementation uses Python's Counter class from the collections module to efficiently solve this problem.

Step-by-step breakdown:

1. Count frequencies: cnt = Counter(nums)

   • This creates a Counter object that automatically counts the frequency of each element in the array
   • For example, if nums = [1, 2, 3, 2], then cnt would be Counter({2: 2, 1: 1, 3: 1})
   • Time complexity: O(n) where n is the length of the array

2. Filter and sum unique elements: sum(x for x, v in cnt.items() if v == 1)

   • cnt.items() returns pairs of (element, count)
   • The generator expression iterates through these pairs
   • if v == 1 filters to keep only elements that appear exactly once
   • x for x, v extracts just the element value (not the count)
   • sum() adds up all these filtered elements
   • Time complexity: O(k) where k is the number of distinct elements

Data Structure Used:

• Counter: A dictionary subclass specifically designed for counting hashable objects. It stores elements as keys and their counts as values.

Pattern Used:

• Filter and Aggregate Pattern: First filter the data based on a condition (count == 1), then aggregate the results (sum).

Overall Complexity:

• Time: O(n) for counting + O(k) for summing = O(n) overall
• Space: O(k) to store the counter, where k ≤ n is the number of distinct elements

Example Walkthrough

Let's walk through the solution with nums = [4, 1, 2, 1, 2, 3]:

Step 1: Count frequencies using Counter

cnt = Counter([4, 1, 2, 1, 2, 3])
# Result: Counter({1: 2, 2: 2, 4: 1, 3: 1})

• Element 1 appears 2 times
• Element 2 appears 2 times
• Element 4 appears 1 time
• Element 3 appears 1 time

Step 2: Iterate through counter and filter elements with count == 1

# cnt.items() gives us: [(4, 1), (1, 2), (2, 2), (3, 1)]
# Let's trace through the generator expression:

• (4, 1): count is 1 ✓ → include 4
• (1, 2): count is 2 ✗ → skip
• (2, 2): count is 2 ✗ → skip
• (3, 1): count is 1 ✓ → include 3

Step 3: Sum the filtered elements

sum([4, 3])  # Elements that appear exactly once
# Result: 7

The final answer is 7, which is the sum of all elements that appear exactly once (4 and 3).

This approach efficiently identifies unique elements in just two passes: one to build the frequency counter and one to sum the unique elements.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the input array nums.

• Creating the Counter object requires iterating through all elements in nums once: O(n)
• The sum operation with generator expression iterates through the Counter's items (at most n unique elements): O(n)
• Overall time complexity is O(n) + O(n) = O(n)

Space Complexity: O(n) where n is the length of the input array nums.

• The Counter object stores frequency counts for each unique element in nums
• In the worst case (all elements are unique), the Counter stores n key-value pairs: O(n)
• The generator expression doesn't create additional space beyond temporary variables: O(1)
• Overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting Manual Frequency Counting with Incorrect Logic

A common mistake is trying to manually count frequencies without properly handling all cases, leading to incorrect results:

Incorrect Approach:

def sumOfUnique(self, nums: List[int]) -> int:
    seen = set()
    duplicates = set()
  
    for num in nums:
        if num in seen:
            duplicates.add(num)
        seen.add(num)
  
    # Wrong: This sums elements that appear at least once but not in duplicates
    # But it misses that elements in duplicates should be excluded entirely
    return sum(num for num in seen if num not in duplicates)

Problem: This approach fails because it doesn't distinguish between elements appearing exactly once versus multiple times. An element appearing three times would be marked as duplicate but still counted.

Correct Manual Approach:

def sumOfUnique(self, nums: List[int]) -> int:
    freq = {}
    # Properly count all frequencies
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
  
    # Sum only elements with frequency exactly 1
    return sum(num for num, count in freq.items() if count == 1)

2. Confusing Unique with Distinct Elements

Incorrect Understanding:

def sumOfUnique(self, nums: List[int]) -> int:
    # Wrong: This returns sum of all distinct elements
    return sum(set(nums))

Problem: The term "unique" in this problem means elements appearing exactly once, not just distinct elements. Using set(nums) gives all distinct elements regardless of their frequency.

Example where this fails:

• Input: [1, 2, 2, 3]
• Incorrect output: 1 + 2 + 3 = 6 (sum of distinct elements)
• Correct output: 1 + 3 = 4 (sum of elements appearing once)

3. Inefficient Nested Loop Approach

Inefficient Approach:

def sumOfUnique(self, nums: List[int]) -> int:
    result = 0
    for i in range(len(nums)):
        count = 0
        for j in range(len(nums)):
            if nums[i] == nums[j]:
                count += 1
        if count == 1:
            result += nums[i]
    return result

Problems:

• Time complexity is O(n²) instead of O(n)
• May count the same unique element multiple times if not careful
• Unnecessarily complex for a simple counting problem

Solution: Always use a hash map or Counter for frequency counting problems to achieve O(n) time complexity.