algoadvance

Leetcode 1748. Sum of Unique Elements

Problem Statement

Given an integer array nums, return the sum of all the unique elements of nums. An element of nums is unique if it appears exactly once in the array.

Clarifying Questions

  1. Input Size: What is the maximum size of the array?
    • Typically, constraints might be stated in the problem. If not, assume a reasonable size, for instance, up to 10,000 elements.
  2. Element Range: What are the values of individual elements in the array?
    • Usually, elements are within a certain range like -1000 to 1000, but confirm this if possible.
  3. Time Complexity: Are there any specific time complexity constraints?
    • Aim for a solution that is efficient, ideally O(n), where n is the number of elements in nums.

Strategy

To solve this problem, we can follow these steps:

  1. Use a hash map (unordered_map) to store the count of each element in the array.
  2. Traverse the array and populate the hash map with the frequency of each element.
  3. Traverse the hash map to sum up elements that have a frequency of exactly 1.

Code

Here’s the implementation in C++:

#include <iostream>
#include <vector>
#include <unordered_map>

int sumOfUnique(std::vector<int>& nums) {
    std::unordered_map<int, int> freqMap;
    
    // Populate frequency map
    for(const int& num : nums) {
        freqMap[num]++;
    }
    
    int sum = 0;
    // Sum up elements with frequency exactly 1
    for(const auto& entry : freqMap) {
        if(entry.second == 1) {
            sum += entry.first;
        }
    }
    
    return sum;
}

int main() {
    std::vector<int> nums = {1, 2, 3, 2};
    std::cout << "Sum of unique elements: " << sumOfUnique(nums) << std::endl;
    return 0;
}

Time Complexity

Feel free to run the provided code with different input cases to verify its correctness. If you have any additional questions or need further clarifications, please let me know!

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