1748. Sum of Unique Elements
Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 75.0%
Problem Breakdown
The problem requires us to find the sum of unique elements in an integer array nums. Unique elements are those that appear exactly once in the array. The input is a list of integers, and the output should be a single integer representing the sum of these unique elements.
Inputs:
- An integer array
numswhere each element is between 1 and 100 inclusive. - The length of
numsis between 1 and 100.
Outputs:
- An integer representing the sum of all unique elements in
nums.
Implicit Constraints or Tricky Edge Cases:
- If there are no unique elements, the output should be 0.
- All elements are positive integers within a small range (1 to 100), which can be useful for optimizing space usage.
Intuition
A brute-force approach would involve checking each element in the array and counting its occurrences. This would require nested loops, resulting in a time complexity of O(n^2). Given the constraints, this is inefficient.
The key insight is to use a hash table (dictionary) to count the occurrences of each element in a single pass through the array. This reduces the time complexity to O(n), where n is the length of the array. After counting, we can iterate over the dictionary to sum up elements that appear exactly once.
Approach
- Initialize a Hash Table: Use a dictionary to store the count of each element in
nums. - Count Occurrences: Iterate through the array and update the count for each element in the dictionary.
- Sum Unique Elements: Iterate over the dictionary and sum up elements that have a count of exactly one.
- Return the Result: The result is the sum of all unique elements.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array
nums. We make two passes through the array: one for counting and one for summing. - Space Complexity: O(k), where k is the number of unique elements in
nums. In the worst case, this could be O(n) if all elements are unique.
Solution
def sumOfUnique(nums):
# Step 1: Initialize a hash table to count occurrences
count = {}
# Step 2: Count occurrences of each element
for num in nums:
if num in count:
count[num] += 1
else:
count[num] = 1
# Step 3: Sum elements that appear exactly once
unique_sum = 0
for num, cnt in count.items():
if cnt == 1:
unique_sum += num
# Step 4: Return the result
return unique_sum
Edge Cases Handled
- All Elements Unique: If all elements are unique, the sum will be the sum of all elements.
- No Unique Elements: If no element appears exactly once, the sum will be 0.
- Single Element Array: The function correctly handles arrays with a single element.
- Array with Duplicates: The function correctly sums only those elements that appear exactly once.