Sum of Unique Elements
EasyPrompt
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.
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 <= 1001 <= nums[i] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each element of the array and, for each element, performs another iteration through the entire array to count its occurrences. If an element's count is exactly one, it's added to the total sum.
Algorithm
- Initialize a variable
sumto 0. - Iterate through the array
numswith an outer loop, fromi = 0ton-1. - For each element
nums[i], initialize acountto 0. - Start an inner loop, from
j = 0ton-1. - Inside the inner loop, if
nums[i] == nums[j], incrementcount. - After the inner loop finishes, check if
count == 1. - If
countis 1, addnums[i]tosum. - After the outer loop finishes, return
sum.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. It involves a nested loop structure. The outer loop picks an element, and the inner loop iterates through the entire array to count how many times that element appears. If the final count for an element is one, it is considered unique and is added to a running total.
Algorithm Steps:
- Initialize a variable
sumto 0. - Loop through the array
numswith an indexi. - For each element
nums[i], initialize a countercountto 0. - Start a nested loop with an index
jto iterate through the array again. - If
nums[i]is the same asnums[j], incrementcount. - After the inner loop completes, if
countis exactly 1, addnums[i]tosum. - Once the outer loop is finished, return the total
sum.
class Solution { public int sumOfUnique(int[] nums) { int sum = 0; for (int i = 0; i < nums.length; i++) { int count = 0; for (int j = 0; j < nums.length; j++) { if (nums[i] == nums[j]) { count++; } } if (count == 1) { sum += nums[i]; } } return sum; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. For each element, we iterate through the entire array again, leading to a quadratic time complexity.
Space
O(1), as we only use a few extra variables to store the sum and count, regardless of the input size.
Trade-offs
Pros
Simple to conceptualize and implement.
Requires no additional data structures, resulting in constant space complexity.
Cons
Highly inefficient for larger arrays due to the O(n^2) time complexity.
Will likely result in a 'Time Limit Exceeded' error on platforms with larger test cases not constrained like this one.
Leveraging the problem's constraint that numbers are between 1 and 100, this approach uses a simple array as a direct-access table to count frequencies. This is more efficient than a hash map as it avoids hashing overhead and uses constant space.
Algorithm
- Create an integer array
countsof size 101, initialized to all zeros. - For each
numinnums:- Increment
counts[num].
- Increment
- Initialize
sum = 0. - For
ifrom 1 to 100:- If
counts[i] == 1, additosum.
- If
- Return
sum.
Walkthrough
Given the constraint that all numbers in nums are between 1 and 100, we can use a simple array as a frequency counter instead of a hash map. This is a form of counting sort and is the most efficient method for this specific problem.
Algorithm Steps:
- Declare an integer array
countsof size 101 (to cover indices 1 through 100) and initialize all its elements to 0. - Iterate through the input array
nums. For eachnum, increment the count at the corresponding index:counts[num]++. - Initialize a variable
sumto 0. - Iterate through the
countsarray from index 1 to 100. - If
counts[i]is equal to 1, it means the numberiappeared exactly once. Addito thesum. - After the loop, return the
sum.
class Solution { public int sumOfUnique(int[] nums) { int[] counts = new int[101]; // Constraints: 1 <= nums[i] <= 100 for (int num : nums) { counts[num]++; } int sum = 0; for (int i = 1; i <= 100; i++) { if (counts[i] == 1) { sum += i; } } return sum; }}Complexity
Time
O(n + m), where n is the length of `nums` and m is the range of possible values (101). Since m is a constant, the complexity simplifies to O(n).
Space
O(m), where m is the range of values (101). Since this size is constant and does not depend on the input size n, the space complexity is considered O(1).
Trade-offs
Pros
Extremely efficient in both time and space.
Simpler to implement than a hash map, with no overhead from hashing or object creation.
Best possible performance given the problem's constraints.
Cons
This solution is not general. It relies heavily on the constraint that the numbers are within a small, known, non-negative range.
This approach uses a hash map to efficiently count the occurrences of each number in the array. It involves two passes: one to populate the frequency map and another to iterate through the map to sum up the elements that appeared only once.
Algorithm
- Create a
HashMap<Integer, Integer>calledfrequencyMap. - For each
numinnums:- Increment the count for
numinfrequencyMap.
- Increment the count for
- Initialize
sum = 0. - For each entry
(number, count)infrequencyMap:- If
count == 1, addnumbertosum.
- If
- Return
sum.
Walkthrough
A more optimized approach involves using a hash map to store the frequency of each number. This avoids the nested loop and reduces the time complexity significantly.
Algorithm Steps:
- Create a
HashMap<Integer, Integer>to store each number and its corresponding frequency. - Iterate through the
numsarray. For each numbernum, update its count in the map. A helper method likemap.getOrDefault(key, defaultValue)is useful here. - Initialize a variable
sumto 0. - Iterate through the key-value pairs (entries) of the hash map.
- For each entry, if its value (the frequency) is 1, add its key (the number) to the
sum. - Return the final
sum.
import java.util.HashMap;import java.util.Map; class Solution { public int sumOfUnique(int[] nums) { Map<Integer, Integer> frequencyMap = new HashMap<>(); for (int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1); } int sum = 0; for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) { if (entry.getValue() == 1) { sum += entry.getKey(); } } return sum; }}Complexity
Time
O(n), where n is the number of elements in `nums`. The first pass to build the map takes O(n) time. The second pass to iterate through the map takes O(k) time, where k is the number of unique elements (k <= n). Thus, the total time complexity is O(n).
Space
O(k), where k is the number of unique elements in the array. In the worst-case scenario where all elements are unique, the space complexity becomes O(n).
Trade-offs
Pros
Significantly faster than the brute-force approach with linear time complexity.
A general solution that works even if the range of numbers is large or unknown.
Cons
Requires extra space to store the hash map, which can be significant if there are many unique elements.
Solutions
Solution
class Solution {public int sumOfUnique(int[] nums) { int[] cnt = new int[101]; for (int x : nums) { ++cnt[x]; } int ans = 0; for (int x = 0; x < 101; ++x) { if (cnt[x] == 1) { ans += x; } } return ans; }}class Solution {public: int sumOfUnique(vector<int> &nums) { int cnt[101]{}; for (int &x : nums) { ++cnt[x]; } int ans = 0; for (int x = 0; x < 101; ++x) { if (cnt[x] == 1) { ans += x; } } return ans; }};class Solution: def sumOfUnique(self, nums: List[int]) -> int: cnt = Counter(nums) return sum(x for x, v in cnt . items() if v == 1)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.