Skip to main content

Hashing

Sum of Unique Elements

Problem Description

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array. Return the sum of all the unique elements of nums.

Example

Input: nums = [1,2,3,2]
Output: 4
Explanation: The unique elements are [1,3], and the sum is 4.

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: There are no unique elements, and the sum is 0.

Constraints

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
💡
Try it Yourself First
The main task is to identify the unique elements in the array—those that appear exactly once. Once we have them, calculating their sum becomes straightforward. Let’s dive into how we can achieve this.

Brute Force Approach


Intuition

How can we identify which elements appear exactly once in an array? Let’s start with the simplest possible idea:

  • For each element in the array, let’s count how many times it appears in the array.
  • If it appears exactly once, it is unique, so we’ll add it to our sum.

This approach is called brute force because it involves checking every element against all the others, without trying to optimize. It’s like solving a problem by brute strength—slow, but it works.

Counting the Frequency of an Element

Imagine we pick the first element in the array, say nums[0]. How do we know how many times it appears?

We check every other element in the array to see if it matches nums[0]. Also we will initialize a count that will count the number of times the matching value appears, for a unique element the count will be 1.

How to compare an element against other elements?

This is where the idea of nested loops comes into play.

What Are Nested Loops?

A nested loop means having one loop inside another. In this case:

  • The outer loop will pick each element in the array, one by one.
  • The inner loop will compare that element with all the elements in the array to count how many times it appears.

How Does It Work?

  1. Outer Loop: Start with the first element (nums[0]), then move to the second element (nums[1]), and so on. This loop ensures that every element gets a chance to be checked.
  2. Inner Loop: For each element selected by the outer loop, we start another loop to scan the entire array and count how many elements match the selected one.

Example

Let’s say the array is [2, 3, 2, 4, 5, 4].

The outer loop picks nums[0] = 2.

The inner loop compares nums[0] with every element in the array:

  • Compare nums[0] with nums[0] → Match (count = 1).
  • Compare nums[0] with nums[1] → No match.
  • Compare nums[0] with nums[2] → Match (count = 2).
  • Continue this process for all elements.

At the end of the inner loop, we know 2 appears 2 times. So it’s not unique.

Next, the outer loop moves to nums[1] = 3, and the inner loop repeats the process for 3.

For 3, we find it appears once → it’s unique.

For 4, it appears twice → not unique.

For 5, it appears once → it’s unique.

Approach

Step 1: Initialize Variables

  • We need a variable, say sum, to store the sum of all unique elements.
  • Set it to 0 initially, as no numbers have been processed yet.

Step 2: Outer Loop to Pick Each Element

  • Use the outer loop to pick one element of the array at a time. Let’s say we’re starting with nums[0].

Step 3: Inner Loop to Count Frequency

  • For the selected element, use an inner loop to compare it with every other element in the array.
  • Keep a count variable to track how many times the current element appears.

Step 4: Check Uniqueness

  • After counting the frequency, check if the count is equal to 1.
  • If it is, add the element to sum.

Step 5: Repeat for All Elements

  • Repeat this process for all elements in the array.

Step 6: Return the Result

  • After processing all elements, return the value of sum.

Dry Run

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

Initial State:

  • sum = 0 (to store the sum of unique elements).

We will use two loops:

  • Outer loop (i) to pick each element.
  • Inner loop (j) to count how many times the current element (nums[i]) appears in the array.

Step-by-Step Execution:Outer Loop (i = 0, nums[0] = 1):

  1. Pick the first element: nums[0] = 1.
  2. Initialize count = 0.

Inner Loop (j from 0 to 3):

  • Compare nums[0] (1) with every element in the array:
    • nums[0] == nums[0] → Match → count = 1.
    • nums[0] == nums[1] → No match → count = 1.
    • nums[0] == nums[2] → No match → count = 1.
    • nums[0] == nums[3] → No match → count = 1.

Result:

  • The count of nums[0] = 1 is 1 (unique).
  • Add 1 to sum.
  • sum = 0 + 1 = 1.

Outer Loop (i = 1, nums[1] = 2):

  1. Pick the second element: nums[1] = 2.
  2. Initialize count = 0.

Inner Loop (j from 0 to 3):

  • Compare nums[1] (2) with every element in the array:
    • nums[1] == nums[0] → No match → count = 0.
    • nums[1] == nums[1] → Match → count = 1.
    • nums[1] == nums[2] → No match → count = 1.
    • nums[1] == nums[3] → Match → count = 2.

Result:

  • The count of nums[1] = 2 is 2 (not unique).
  • Do not add to sum.
  • sum = 1 (unchanged).

Outer Loop (i = 2, nums[2] = 3):

  1. Pick the third element: nums[2] = 3.
  2. Initialize count = 0.

Inner Loop (j from 0 to 3):

  • Compare nums[2] (3) with every element in the array:
    • nums[2] == nums[0] → No match → count = 0.
    • nums[2] == nums[1] → No match → count = 0.
    • nums[2] == nums[2] → Match → count = 1.
    • nums[2] == nums[3] → No match → count = 1.

Result:

  • The count of nums[2] = 3 is 1 (unique).
  • Add 3 to sum.
  • sum = 1 + 3 = 4.

Outer Loop (i = 3, nums[3] = 2):

  1. Pick the fourth element: nums[3] = 2.
  2. Initialize count = 0.

Inner Loop (j from 0 to 3):

  • Compare nums[3] (2) with every element in the array:
    • nums[3] == nums[0] → No match → count = 0.
    • nums[3] == nums[1] → Match → count = 1.
    • nums[3] == nums[2] → No match → count = 1.
    • nums[3] == nums[3] → Match → count = 2.

Result:

  • The count of nums[3] = 2 is 2 (not unique).
  • Do not add to sum.
  • sum = 4 (unchanged).

Final Result:

After completing all iterations of the outer loop:

  • The unique elements are [1, 3].
  • The sum of unique elements is 4.
Code for All Languages
C++ 
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        
        // Step 1: Initialize sum to store the result
        int sum = 0; 
        
        // Step 2: Outer loop to pick each element
        for (int i = 0; i < nums.size(); i++) {
            
            // Step 3: Initialize count for the current element
            int count = 0; 
            
            // Step 3: Inner loop to count frequency of nums[i]
            for (int j = 0; j < nums.size(); j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }
            
            // Step 4: Check uniqueness and add to sum if unique
            if (count == 1) {
                sum += nums[i];
            }
        }
        
        // Step 6: Return the result
        return sum;
    }
};

int main() {
    
    // Input size of the array
    int n;
    cin >> n; 
    
    // Declare a vector to store the array elements
    vector<int> nums(n);
    
    // Input elements of the array
    for (int i = 0; i < n; i++) {
        cin >> nums[i]; 
    }
    
    // Create an instance of the Solution class
    Solution sol;
    
    // Call the function and print the result
    cout << sol.sumOfUnique(nums) << endl; 
    
    return 0;
}

Java 
import java.util.Scanner;

class Solution {
    public int sumOfUnique(int[] nums) {
        
        // Step 1: Initialize sum to store the result
        int sum = 0; 
        
        // Step 2: Outer loop to pick each element
        for (int i = 0; i < nums.length; i++) {
            
            // Step 3: Initialize count for the current element
            int count = 0; 
            
            // Step 3: Inner loop to count frequency of nums[i]
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    count++;
                }
            }
            
            // Step 4: Check uniqueness and add to sum if unique
            if (count == 1) {
                sum += nums[i];
            }
        }
        
        // Step 6: Return the result
        return sum;
    }
}

public class Main {
    public static void main(String[] args) {
        
        // Input size of the array
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 
        
        // Declare an array to store the array elements
        int[] nums = new int[n];
        
        // Input elements of the array
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt(); 
        }
        
        // Create an instance of the Solution class
        Solution sol = new Solution();
        
        // Call the function and print the result
        System.out.println(sol.sumOfUnique(nums)); 
        
        sc.close();
    }
}

Python 
from typing import List

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        
        # Step 1: Initialize sum to store the result
        sum = 0
        
        # Step 2: Outer loop to pick each element
        for i in range(len(nums)):
            
            # Step 3: Initialize count for the current element
            count = 0
            
            # Step 3: Inner loop to count frequency of nums[i]
            for j in range(len(nums)):
                if nums[i] == nums[j]:
                    count += 1
            
            # Step 4: Check uniqueness and add to sum if unique
            if count == 1:
                sum += nums[i]
        
        # Step 6: Return the result
        return sum


# Input handling
if __name__ == "__main__":
    # Step 1: Input size of the array
    n = int(input()) 
    
    # Step 2: Input the elements of the array
    nums = list(map(int, input().split())) 
    
    # Step 3: Create an instance of the Solution class
    sol = Solution()
    
    # Step 4: Call the function and print the result
    print(sol.sumOfUnique(nums))

Javascript 
var uniqueOccurrences = function(arr) {
    
    // Step 1: Initialize a variable to store the sum of unique elements
    let sum = 0;
    
    // Step 2: Outer loop to pick each element
    for (let i = 0; i < arr.length; i++) {
        
        // Step 3: Initialize count for the current element
        let count = 0;
        
        // Step 3: Inner loop to count the frequency of arr[i]
        for (let j = 0; j < arr.length; j++) {
            if (arr[i] === arr[j]) {
                count++;
            }
        }
        
        // Step 4: Check uniqueness and add to sum if unique
        if (count === 1) {
            sum += arr[i];
        }
    }
    
    // Step 5: Return the result
    return sum;
};

// Input handling
let n = parseInt(prompt());  // size of the array
let arr = prompt().split(' ').map(Number);  // input the array elements

// Output the result
console.log(uniqueOccurrences(arr));  // Output the sum of unique elements

Time Complexity : O(n²)

Loop Execution:

  1. Outer Loop:
    • The outer loop runs n times, where n is the number of elements in the array (nums).
    • For each iteration of the outer loop, the inner loop is executed.
  3. Inner Loop:
    • For each element in the outer loop, the inner loop compares it with all n elements of the array to count its frequency. This involves n comparisons.

Thus, the nested loop runs n * n times (i.e., the inner loop runs n times for each of the n iterations of the outer loop).

  1. Operations inside the Loops:
    • Inside the inner loop, we perform a comparison (nums[i] == nums[j]), which takes constant time, O(1).
    • If the element is unique (after the inner loop finishes), adding it to the sum also takes O(1).

Final Time Complexity:

  • The total time complexity is O(n²), as the nested loops dominate the execution time.

Space Complexity

Auxiliary Space Complexity: O(1)

  • The auxiliary space refers to the extra space used by the algorithm apart from the input.
  • In this case, we are using only a few variables:
    • sum (to store the result).
    • count (to track the frequency of the current element).
  • These variables require constant space, O(1).

Total Space Complexity: O(n)

  • The total space includes both the input and the auxiliary space.
  • The input array nums takes O(n) space, where n is the number of elements in the array.
  • The algorithm does not use any additional space proportional to the size of the input, except for the constant variables.

Final Space Complexity: O(n).

In the previous approach the nested loops make the approach inefficient for large inputs since it takes quadratic time, which grows quickly as the array size increases. Can we think of a way to track the frequency of elements without comparing each value to all others, reducing the time complexity?

Optimal Approach


Intuition

Imagine you are organizing a party, and you want to find out how many times each guest has visited your party in the past.

  • You have a list of guests from different occasions: ["Alice", "Bob", "Alice", "Charlie", "Alice", "Bob"].
  • Instead of manually counting every time Alice or Bob appears in the list, you create a chart:
    • Write each guest's name in the chart, and every time you see their name in the list, you increase their count.
    • At the end, your chart looks like this:
      Alice: 3
      Bob: 2
      Charlie: 1

This chart allows you to see how many times each person has visited, without needing to repeatedly compare their names in the original list.

In the same way, in our problem, we have an array of numbers, and we want to count how many times each number appears.

  • Instead of repeatedly comparing one number to all others (as we did in the brute force approach), we can create a "chart" (or map) that keeps track of the count of each number as we go through the array.
  • This technique is called Hashing in programming and the "chart" in programming is called a hash table or a hash map.

What is Hashing?

Hashing is a technique used in DSA to map data to a fixed-size array (called a hash table) using a hash function. This mapping ensures efficient data retrieval, insertion, and deletion in constant average time, O(1). A hashmap is a key-value pair implementation that uses hashing to store and retrieve data efficiently.

What to use here Hash Table or Hash Map and Why?

For this problem, we should use a Hash Map instead of a Hash Table. A Hash Map is more efficient and flexible because:

  1. Dynamic Sizing: Hash Maps automatically adjust their size as data grows, ensuring better performance even for large inputs.
  2. Efficiency: Hash Maps support faster lookups, insertions, and deletions with an average time complexity of O(1).
  3. Modern Implementation: Hash Maps are the preferred choice in most programming languages (e.g., unordered_map in C++ or HashMap in Java) for advanced tasks.

Thus, Hash Map is the better option for counting frequencies and summing unique elements efficiently.

Approach

Step 1: Initialize the Hash Map

  • Create an empty hash map to store the frequency of each element.
  • In most languages:
    • Use unordered_map in C++.
    • Use HashMap in Java.
    • Use a dictionary {} in Python.
    • Use a Map in Javascript

Step 2: Count the Frequency of Each Element

  • Traverse the array once.
  • For each element:
    • If the element is already in the hash map, increment its count.
    • If not, add it to the hash map with a count of 1.

Step 3: Sum the Unique Elements

  • Initialize a variable sum to 0 to store the result.
  • Iterate through the hash map.
  • For each element (key-value pair), check if the value (frequency) is 1:
    • If yes, add the key (element) to sum.

Step 4: Return the Result

  • Return the final value of sum.

Dry Run

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

Goal : Identify the unique elements (those appearing exactly once) and calculate their sum. Unique elements = [1, 3]. Sum = 1 + 3 = 4.

Step 1: Initialize the Hash Map

We start by creating an empty Map called frequency.

Initially: frequency = Map {}


Step 2: Count the Frequency of Each Element

We iterate over the array nums using a loop and update the Map to store the count of each element.

Iteration 1:

Process nums[0] = 1

  • Check if 1 is in the Map → No.
  • Add 1 to the Map with a count of 1.

Updated frequency: frequency = Map { 1 => 1 }

Iteration 2:

Process nums[1] = 2

  • Check if 2 is in the Map → No.
  • Add 2 to the Map with a count of 1.

Updated frequency: frequency = Map { 1 => 1, 2 => 1 }

Iteration 3:

Process nums[2] = 3

  • Check if 3 is in the Map → No.
  • Add 3 to the Map with a count of 1.

Updated frequency: frequency = Map { 1 => 1, 2 => 1, 3 => 1 }

Iteration 4:

Process nums[3] = 2

  • Check if 2 is in the Map → Yes.
  • Increment the count of 2 in the Map by 1.

Updated frequency: frequency = Map { 1 => 1, 2 => 2, 3 => 1 }


Step 3: Sum the Unique Elements

Now that we have the frequency of each element, we iterate over the Map and sum the elements with a frequency of 1.

Iteration 1:

Process Key 1 (Frequency 1)

  • Check if frequency of 1 is 1 → Yes.
  • Add 1 to the sum.

Running sum: sum = 1

Iteration 2:

Process Key 2 (Frequency 2)

  • Check if frequency of 2 is 1 → No.
  • Skip this key.

Running sum: sum = 1

Iteration 3:

Process Key 3 (Frequency 1)

  • Check if frequency of 3 is 1 → Yes.
  • Add 3 to the sum.

Final sum: sum = 1 + 3 = 4


Step 4: Return the Result

Return the value of sum, which is 4.

Final Output : Output: 4

Code for All Languages
C++ 
#include <iostream>
#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        
        // Step 1: Create a map to store the frequency of each element
        map<int, int> frequencyMap;
        
        // Step 2: Iterate through the array to fill the frequency map
        for (int i = 0; i < nums.size(); i++) {
            frequencyMap[nums[i]]++;
        }
        
        // Step 3: Initialize sum to store the result
        int sum = 0;
        
        // Step 4: Iterate through the map and sum up the elements with frequency 1
        for (auto& entry : frequencyMap) {
            if (entry.second == 1) {
                sum += entry.first;
            }
        }
        
        // Step 5: Return the result
        return sum;
    }
};

int main() {
    
    // Input size of the array
    int n;
    cin >> n; 
    
    // Declare a vector to store the array elements
    vector<int> nums(n);
    
    // Input elements of the array
    for (int i = 0; i < n; i++) {
        cin >> nums[i]; 
    }
    
    // Create an instance of the Solution class
    Solution sol;
    
    // Call the function and print the result
    cout << sol.sumOfUnique(nums) << endl; 
    
    return 0;
}

Java 
import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int sumOfUnique(int[] nums) {
        
        // Step 1: Create a map to store the frequency of each element
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Step 2: Iterate through the array to fill the frequency map
        for (int i = 0; i < nums.length; i++) {
            frequencyMap.put(nums[i], frequencyMap.getOrDefault(nums[i], 0) + 1);
        }
        
        // Step 3: Initialize sum to store the result
        int sum = 0;
        
        // Step 4: Iterate through the map and sum up the elements with frequency 1
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getValue() == 1) {
                sum += entry.getKey();
            }
        }
        
        // Step 5: Return the result
        return sum;
    }
}

public class Main {
    public static void main(String[] args) {
        
        // Input size of the array
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); 
        
        // Declare an array to store the array elements
        int[] nums = new int[n];
        
        // Input elements of the array
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt(); 
        }
        
        // Create an instance of the Solution class
        Solution sol = new Solution();
        
        // Call the function and print the result
        System.out.println(sol.sumOfUnique(nums)); 
        
        sc.close();
    }
}

Python 
from typing import List

class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        
        # Step 1: Create a dictionary to store the frequency of each element
        frequency_map = {}
        
        # Step 2: Iterate through the array to fill the frequency map
        for num in nums:
            frequency_map[num] = frequency_map.get(num, 0) + 1
        
        # Step 3: Initialize sum to store the result
        total_sum = 0
        
        # Step 4: Iterate through the frequency map and sum up elements with frequency 1
        for num, count in frequency_map.items():
            if count == 1:
                total_sum += num
        
        # Step 5: Return the result
        return total_sum


# Input handling
if __name__ == "__main__":
    # Step 1: Input size of the array
    n = int(input())
    
    # Step 2: Input the elements of the array
    nums = list(map(int, input().split()))
    
    # Step 3: Create an instance of the Solution class
    sol = Solution()
    
    # Step 4: Call the function and print the result
    print(sol.sumOfUnique(nums))

Javascript 
var uniqueOccurrences = function(arr) {
    
    // Step 1: Create a map to store the frequency of each element
    let frequencyMap = new Map();
    
    // Step 2: Iterate through the array to fill the frequency map
    for (let i = 0; i < arr.length; i++) {
        frequencyMap.set(arr[i], (frequencyMap.get(arr[i]) || 0) + 1);
    }
    
    // Step 3: Initialize sum to store the result
    let sum = 0;
    
    // Step 4: Iterate through the map and sum the elements with frequency 1
    frequencyMap.forEach((count, num) => {
        if (count === 1) {
            sum += num;
        }
    });
    
    // Step 5: Return the result
    return sum;
};

// Input handling
let n = parseInt(prompt());  // size of the array
let arr = prompt().split(' ').map(Number);  // input the array elements

// Output the result
console.log(uniqueOccurrences(arr));  // Output the sum of unique elements

Time Complexity : O(n)

Loop Execution

  1. First Loop (Counting Frequency):
    • The first loop iterates over the array nums, which runs n times, where n is the number of elements in the array.
    • For each element, we update the frequency in the hash map using the set and get operations, which both take constant time O(1) on average.
    • Thus, the first loop runs in O(n) time.
  3. Second Loop (Summing Unique Elements):
    • After counting the frequencies, we iterate through all the entries in the hash map, which contains at most n entries (one for each unique element in the array).
    • For each entry, we check the frequency and, if it's 1, add the key (element) to the sum. This takes constant time O(1) per entry.
    • Therefore, this loop also runs in O(n) time.

Operations Inside the Loops

  • First Loop (Frequency Count): Each insertion or update in the hash map takes O(1) time.
  • Second Loop (Summation): Each frequency check and summation operation also takes O(1) time.

Final Time Complexity

  • The two loops are sequential (not nested), so their time complexities add up: O(n) + O(n) = O(n).

Space Complexity : O(n)

Auxiliary Space Complexity: O(n)

  • The auxiliary space refers to the extra space used by the algorithm apart from the input.
  • In this case, we are using a hash map (frequency) to store the frequency count of each element.
  • The hash map can hold up to n entries, where n is the number of elements in the input array nums. Each entry in the hash map requires constant space O(1).
  • Thus, the auxiliary space used by the hash map is O(n).

Total Space Complexity: O(n)

  • The total space includes both the input and the auxiliary space:
    1. The input array nums takes O(n) space, where n is the number of elements in the array.
    2. The hash map (frequency) also takes O(n) space to store frequency counts.
  • No additional space proportional to the input size is used, except for the hash map.

Final Space Complexity

  • Since the input and hash map both contribute O(n) space, the overall space complexity is O(n).

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Sum of Unique Elements

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.