Leetcode – Sum of Unique Elements Solution

Spread the love

One of the challenges available on Leetcode is the “Sum of Unique Elements” problem, a fascinating exercise in array manipulation and hashing. In this extensive guide, we’ll break down the problem statement, examine multiple ways to approach the problem, and analyze the performance of each approach.

Problem Statement

The objective of the “Sum of Unique Elements” problem is simple yet compelling. Given an integer array nums, you need to return the sum of unique elements in that array.

Input:

  • An integer array nums (1≤ ∣nums∣ ≤100 )where 1 ≤ nums[i] ≤100.

Output:

  • An integer representing the sum of unique elements in nums.

Example:

Input: nums = [1, 2, 3, 2]

Output: 4

In this example, the unique numbers are 1 and 3, and their sum is 1+3=4.

Brute-Force Approach

The most straightforward approach to solving this problem is to iterate over each element and check its frequency in the array. If the element appears only once, add it to the sum.

Here’s a Python implementation for the same:

def sumOfUnique(nums):
    unique_sum = 0
    
    for num in nums:
        if nums.count(num) == 1:
            unique_sum += num
            
    return unique_sum

Time and Space Complexity Analysis

The time complexity for this solution is O(n^2) because the count() method iterates through the entire array for each element. The space complexity is O(1), as we only use a single integer variable to store the sum. This approach might be inefficient for larger arrays.

Optimized Approach Using Hashing

We can optimize our solution by using a hash table (or dictionary in Python) to store the frequency of each number as we go through the array. This way, we can compute the sum in a single pass.

Here’s the Python code to achieve this:

def sumOfUnique(nums):
    num_count = {}
    unique_sum = 0
    
    for num in nums:
        if num in num_count:
            num_count[num] += 1
        else:
            num_count[num] = 1
            
    for num, count in num_count.items():
        if count == 1:
            unique_sum += num
            
    return unique_sum

Time and Space Complexity Analysis

The time complexity for this solution is O(n), where n is the length of the input array. This is because we go through the array twice: once to populate the hash table and once to sum up the unique elements. The space complexity is O(n) due to the extra hash table used for storing frequencies.

Further Refinement: One-Pass Solution

We can slightly modify our previous solution to get the sum in a single pass through the array.

Here’s how:

def sumOfUnique(nums):
    num_count = {}
    unique_sum = 0
    
    for num in nums:
        if num in num_count:
            # If we have already added this unique element to unique_sum, we remove it.
            if num_count[num] == 1:
                unique_sum -= num
            num_count[num] += 1
        else:
            num_count[num] = 1
            unique_sum += num
            
    return unique_sum

Time and Space Complexity Analysis

The time complexity remains O(n), and the space complexity is also O(n).

Test Cases

After implementing the solution, it’s important to validate its correctness with test cases:

assert sumOfUnique([1, 2, 3, 2]) == 4
assert sumOfUnique([1, 1, 1, 1, 1]) == 0
assert sumOfUnique([1, 2, 3, 4, 5]) == 15
assert sumOfUnique([]) == 0
assert sumOfUnique([100]) == 100

Conclusion

The “Sum of Unique Elements” problem on Leetcode is an excellent problem to test one’s understanding of array manipulation and hashing. It offers a good balance between complexity and simplicity, making it suitable for both beginners and those looking for a quick challenge. Through this problem, we also see how an optimized approach can dramatically improve the performance, taking the solution from O(n^2) to O(n).

Leave a Reply