1748. Sum of Unique Elements

EasyArrayHash TableCounting

Problem Description

The problem is centered on being presented with an array nums that consists of integer elements. The primary task is to calculate the sum of the unique elements within this array. An element is considered unique if it appears only once in the array. Thus, if an element appears more than once, it should not be included in the sum.

For example, if the nums array is [1, 2, 2, 3, 4], the unique elements are 1, 3, and 4 as they appear exactly once. Adding these up gives us a sum of 1 + 3 + 4 = 8.

Intuition

The intuition behind the solution is to first identify the unique elements. To do this systematically, we need to go through the array and keep track of the frequency or count of each element. This can be done efficiently using a hash map, which allows constant time insertions and lookups.

In Python, the Counter class from the collections module does exactly this – it creates a dictionary where keys are the elements of the array and values are the counts of those elements.

Once we have the frequency counts, the next step is to iterate over the count dictionary and collect all keys (the array elements) that have a count of exactly one (1), which indicates that they are unique. The final step is to sum up all these keys to get the desired output.

This approach is efficient because it operates in linear time, dependent on the size of the input array. The space used by the Counter may vary, but in the worst case, if all elements are unique, it will be proportional to the size of the input array.

Solution Approach

The solution provided uses Python's Counter from the collections module, which is a subclass of dict. Essentially, it is a dictionary where elements are stored as dictionary keys and their counts are stored as dictionary values.

Here's the step-by-step approach to the solution:

We instantiate a Counter with the nums array: cnt = Counter(nums). At this point, cnt is a dictionary-like object where each key is a number from the nums array and the corresponding value is how many times that number appears in nums.
Next, we iterate through this Counter dictionary with a generator expression: (x for x, v in cnt.items() if v == 1). This examines each pair of (element, count) in the dictionary. The generator expression yields each element x if its associated count v is exactly 1, which means x is a unique element in the original array.
The unique elements retrieved from the generator expression above are fed directly into the sum() function: return sum(x for x, v in cnt.items() if v == 1). sum() takes an iterable as an argument, and here it cumulatively adds up all of the unique elements which were yielded by the generator expression.

By using a Counter to get the frequencies and a generator expression to filter and sum the unique elements, the solution sorts the problem efficiently in both time and space complexity—in linear time, since each element in the array is processed exactly once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the following nums array: [4, 3, 2, 4, 1].

We first create a Counter with our nums array, resulting in the structure: cnt = Counter([4, 3, 2, 4, 1]). Now, cnt would look like this: {4: 2, 3: 1, 2: 1, 1: 1} where the keys are the numbers from nums and their corresponding values indicate the number of times they appear in nums.
Next, we iterate through the Counter dictionary with a generator expression. To visualize this, we tackle each (element, count) pair:
- (4, 2): Since the count is not 1, 4 is not unique, and we do not consider it for our sum.
- (3, 1): Since the count is 1, 3 is unique, and we consider it for our sum.
- (2, 1): 2 has a count of 1, hence it is unique and included in our sum.
- (1, 1): 1 also has a count of 1, indicating it's unique, so we include it in our sum.
Now, we supply the unique elements yielded from the step above to the sum() function. Our generator expression would yield values 3, 2, and 1 which are the unique numbers.
Finally, the sum() function adds up these yielded values: 3 + 2 + 1 = 6.

The final output of our example would thus be 6, since it is the sum of the unique elements in the provided nums array. This walkthrough demonstrates how the provided solution approach would work with an actual array of integers.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def sumOfUnique(self, nums: List[int]) -> int:
5        # Create a counter object to tally the frequency of each number in the nums list
6        num_counts = Counter(nums)
7      
8        # Calculate and return the sum of all the numbers
9        # that appear exactly once (unique numbers)
10        return sum(number for number, count in num_counts.items() if count == 1)
11

1class Solution {
2    public int sumOfUnique(int[] nums) {
3        // Create an array to keep track of the count of each number
4        int[] count = new int[101]; // Assuming that the elements in nums are within [1, 100]
5
6        // Iterate over each element in the input array and increment the corresponding count
7        for (int num : nums) {
8            count[num]++;
9        }
10
11        int sum = 0; // Initialize sum to store the sum of unique elements
12
13        // Iterate over the count array
14        for (int i = 0; i < 101; i++) {
15            // If the count of a number is exactly 1, it is unique and add it to the sum
16            if (count[i] == 1) {
17                sum += i;
18            }
19        }
20
21        // Return the sum of all unique elements
22        return sum;
23    }
24}
25

1#include <vector> // Required for the std::vector type
2
3class Solution {
4public:
5    // Function to calculate the sum of all unique elements in the vector nums.
6    int sumOfUnique(vector<int>& nums) {
7        int counts[101] = {0}; // Initialize an array to store the count of each number.
8      
9        // Increment the count for each number in nums.
10        for (int num : nums) {
11            ++counts[num];
12        }
13      
14        int sum = 0; // Variable to hold the sum of unique numbers.
15      
16        // Iterate through the counts array.
17        for (int i = 0; i < 101; ++i) {
18            // If a number occurs exactly once, add it to the sum.
19            if (counts[i] == 1) {
20                sum += i;
21            }
22        }
23      
24        // Return the total sum of unique numbers.
25        return sum;
26    }
27};
28

1// This function calculates the sum of unique numbers in an array.
2// A number is unique if it appears exactly once in the array.
3function sumOfUnique(nums: number[]): number {
4    // Create an array to keep track of the count of each number (0-100) within the nums array.
5    const count = new Array(101).fill(0);
6  
7    // Iterate over the nums array to increment the count at each number's index.
8    for (const num of nums) {
9        ++count[num];
10    }
11  
12    // Initialize sum to store the sum of unique elements.
13    let sum = 0;
14  
15    // Iterate over the count array to check if a number appeared exactly once.
16    for (let i = 0; i <= 100; ++i) {
17        // If the count is exactly 1, add the number to the sum.
18        if (count[i] === 1) {
19            sum += i;
20        }
21    }
22  
23    // Return the total sum of unique numbers.
24    return sum;
25}
26

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the input list nums. This is because the Counter(nums) operation iterates over the list once to count the occurrences of each element, and the sum function iterates over the counted elements once. Both operations are linear in terms of the number of elements in nums.

The space complexity of the code is also O(n) since it stores a count of each unique element in the list nums, creating a dictionary that in the worst case could have as many entries as there are elements in the list, if all elements are unique.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know