algoadvance

Leetcode 1748. Sum of Unique Elements

Problem Statement

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

Clarifying Questions

1. Can the input array contain negative numbers?
   • Yes, the array can contain negative numbers.
2. What is the range of the input array length?
   • The length of the input array can range from 1 to 1000.
3. What is the range of the element values in the array?
   • Each element can be in the range [-1000, 1000].

Strategy

To solve this problem, we’ll use a HashMap to count the occurrences of each element. Here’s the step-by-step strategy:

1. Initialize a HashMap: Use it to count the occurrences of each element in the array.
2. Count Occurrences: Traverse through the array and update the count for each element in the HashMap.
3. Sum Unique Elements: Traverse through the HashMap and sum the elements that have a count of exactly one.
4. Return the Result: Return the computed sum.

Code

public class SumOfUniqueElements {
    public int sumOfUnique(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();

        // Count occurrences of each element
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // Sum up the unique elements
        int sum = 0;
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() == 1) {
                sum += entry.getKey();
            }
        }

        return sum;
    }

    public static void main(String[] args) {
        SumOfUniqueElements obj = new SumOfUniqueElements();
        int[] nums = {1, 2, 3, 2};  // Example input
        System.out.println(obj.sumOfUnique(nums));  // Output should be 1 + 3 = 4
    }
}

Time Complexity

• Counting Occurrences: O(n) where n is the number of elements in the input array, as we are traversing through the array once.
• Summing Unique Elements: O(m) where m is the number of unique elements in the input array, as we are traversing the keys in the countMap. In the worst case, m could be equal to n.
• Overall Time Complexity: O(n) because the operations are linear in relation to the input size.

Space Complexity

• Space Complexity: O(n) which is the space required to store the counts in the HashMap. In the worst case, if all elements are unique, the size of the HashMap will be equal to n.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?