Leetcode 1748. Sum of Unique Elements

Problem

Given an integer array, calculate the sum of all elements that appear exactly once in the array. An element is considered unique if it occurs only one time throughout the entire array.

For example, if the array contains [3, 7, 3, 9], the elements 7 and 9 each appear exactly once, so the answer would be 7 + 9 = 16.

Requirements

1. Identify all elements that appear exactly once in the input array
2. Return the sum of these unique elements
3. If no elements appear exactly once, return 0

Constraints

• 1 ≤ nums.length ≤ 100
• 1 ≤ nums[i] ≤ 100
• Expected time complexity: O(n)
• Expected space complexity: O(n)

Examples

Example 1:

Input: nums = [1, 2, 3, 2] Output: 4 Explanation: The element 1 appears once and the element 3 appears once. The elements that appear exactly once are 1 and 3, so the sum is 1 + 3 = 4.

Example 2:

Input: nums = [1, 2, 3, 4, 5] Output: 15 Explanation: All elements appear exactly once. The sum is 1 + 2 + 3 + 4 + 5 = 15.

Example 3:

Input: nums = [1, 1, 2, 2, 3, 3] Output: 0 Explanation: No elements appear exactly once, so the sum is 0.

Hint 1: Counting Frequencies

Hint 2: Two-Pass Solution Consider making two passes through the data: first to count frequencies, then to sum elements whose frequency equals 1. This separation of concerns makes the logic clearer.

Hint 3: Space-Time Tradeoff Given the small constraint on element values (1 to 100), you could use a simple array instead of a hash map to store frequencies, which might be slightly faster in practice.

Full Solution ` def sumOfUnique(nums): # Count the frequency of each element frequency = {} for num in nums: frequency[num] = frequency.get(num, 0) + 1

# Sum elements that appear exactly once
unique_sum = 0
for num, count in frequency.items():
    if count == 1:
        unique_sum += num

return unique_sum

`

Explanation:

The solution uses a two-pass approach with a hash map:

1. First Pass - Count Frequencies: We iterate through the array once and build a frequency map that records how many times each element appears. We use a dictionary where keys are array elements and values are their occurrence counts.
2. Second Pass - Sum Unique Elements: We iterate through the frequency map and sum all elements whose count is exactly 1. These are the elements that appear only once in the original array.

Alternative One-Pass Approach:

` def sumOfUnique(nums): frequency = {} unique_sum = 0

for num in nums:
    if num not in frequency:
        # First occurrence: add to sum
        frequency[num] = 1
        unique_sum += num
    elif frequency[num] == 1:
        # Second occurrence: remove from sum and mark as duplicate
        frequency[num] = 2
        unique_sum -= num
    # If frequency[num] >= 2, do nothing (already excluded)

return unique_sum

`

This optimized version maintains the sum as we go, adding elements on first occurrence and subtracting them when we find a duplicate.

Time Complexity: O(n) where n is the length of the array. We iterate through the array once (or twice in the first approach), and hash map operations are O(1) on average.

Space Complexity: O(k) where k is the number of distinct elements in the array. In the worst case, k = n when all elements are unique. Given the constraint that values are between 1 and 100, k ≤ 100.