What is the time complexity of the Hash Map Counting approach?

The time complexity is O(n) where n is the length of the array, as we iterate through the array twice - once to count frequencies and once to sum unique elements.

What is the space complexity of the Array Counting approach?

The space complexity is O(1) since we use a fixed-size array of 101 elements regardless of the input size, thanks to the constraint that all elements are between 1 and 100.

Why is the Sorting approach less efficient?

The Sorting approach has O(n log n) time complexity due to the sorting step, which is slower than the O(n) time complexity of the counting approaches.

Which approach is recommended for this problem?

The Array Counting approach is recommended as it has O(n) time complexity and O(1) space complexity, making it the most efficient solution given the problem constraints.

Sum of Unique Elements

Difficulty: Easy | Acceptance: 79.90% | Paid: No Topics: Array, Hash Table, Counting

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array.

Return the sum of all the unique elements of nums.

Examples
Constraints
Hash Map Counting
Array Counting
Sorting Approach

Examples

Example 1

Input: nums = [1,2,3,2]
Output: 4
Explanation:
The unique elements are [1,3], and the sum is 4.

Example 2

Input: nums = [1,1,1,1,1]
Output: 0
Explanation:
There are no unique elements, and the sum is 0.

Example 3

Input: nums = [1,2,3,4,5]
Output: 15
Explanation:
The unique elements are [1,2,3,4,5], and the sum is 15.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100

Hash Map Counting

Intuition Use a hash map to count the frequency of each element, then sum elements that appear exactly once.

Steps

Create a hash map to store the count of each element
Iterate through the array and increment the count for each element
Iterate through the hash map and sum up elements with count equal to 1

python

from typing import List

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
        return sum(num for num, freq in count.items() if freq == 1)

Complexity

Time: O(n) where n is the length of the array
Space: O(n) for the hash map in the worst case
Notes: Simple and intuitive approach, works for any range of values

Array Counting

Intuition Since all elements are between 1 and 100, use a fixed-size array of 101 elements to count frequencies efficiently.

Steps

Create an array of size 101 initialized to 0
Iterate through nums and increment the count at index equal to the element value
Sum up all indices where the count is exactly 1

python

from typing import List

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        count = [0] * 101
        for num in nums:
            count[num] += 1
        return sum(i for i in range(101) if count[i] == 1)

Complexity

Time: O(n) where n is the length of the array
Space: O(1) since the counting array has fixed size 101
Notes: Most space-efficient approach due to the constraint on element values

Sorting Approach

Intuition Sort the array and check each element against its neighbors to determine if it appears exactly once.

Steps

Sort the array in non-decreasing order
Iterate through the array and check if each element is different from both its neighbors
Sum up elements that are unique (different from both neighbors)

python

from typing import List

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        total = 0
        for i in range(n):
            if (i == 0 or nums[i] != nums[i - 1]) and (i == n - 1 or nums[i] != nums[i + 1]):
                total += nums[i]
        return total

Complexity

Time: O(n log n) due to sorting
Space: O(1) or O(n) depending on the sorting algorithm
Notes: Less efficient than counting approaches but demonstrates an alternative method