algoadvance

Given an integer array nums, return the sum of all the unique elements of nums. Unique elements are those elements that appear exactly once in the array.

Clarifying Questions

1. Can the input array contain negative numbers?
   • Yes, the input array can contain negative numbers.
2. What should be returned if all elements are duplicates?
   • If there are no unique elements, the function should return 0.
3. Can the array be empty?
   • Yes, if the array is empty, the function should return 0.

Strategy

1. Use a dictionary to count occurrences:
   • Traverse through the array and use a dictionary to count the frequency of each element.
   • Initialize an empty dictionary.
   • For each element in the array, increment its count in the dictionary.
2. Sum unique elements:
   • Iterate through the dictionary.
   • Sum the keys which have a value of 1 (indicating they are unique).

This method ensures that we count in a single pass through the array (O(n)), and then sum by iterating through the dictionary (O(u), where u is the number of unique elements).

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the array. This is because counting elements and summing unique elements can both be done in linear time.
• Space Complexity: O(n), for storing the frequency of all elements in the dictionary.

Code

def sum_of_unique(nums):
    frequency = {}
    
    # Traverse through the array and count the frequency of each element
    for num in nums:
        if num in frequency:
            frequency[num] += 1
        else:
            frequency[num] = 1
    
    # Sum up the keys where the count is 1 (unique elements)
    unique_sum = 0
    for num, count in frequency.items():
        if count == 1:
            unique_sum += num
    
    return unique_sum

Example

Let’s go through an example:

nums = [1, 2, 3, 2]
print(sum_of_unique(nums))  # Expected output: 4, since 1 and 3 are unique and their sum is 4.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?