Scale Engineer

Sum of Unique Elements

Easy
#1600Time: O(n^2), where n is the number of elements in `nums`. For each element, we iterate through the entire array again, leading to a quadratic time complexity.Space: O(1), as we only use a few extra variables to store the sum and count, regardless of the input size.1 company
Patterns
Counting
Data structures
ArrayHash Table
Companies
tcs

Prompt

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 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through each element of the array and, for each element, performs another iteration through the entire array to count its occurrences. If an element's count is exactly one, it's added to the total sum.

Algorithm

  • Initialize a variable sum to 0.
  • Iterate through the array nums with an outer loop, from i = 0 to n-1.
  • For each element nums[i], initialize a count to 0.
  • Start an inner loop, from j = 0 to n-1.
  • Inside the inner loop, if nums[i] == nums[j], increment count.
  • After the inner loop finishes, check if count == 1.
  • If count is 1, add nums[i] to sum.
  • After the outer loop finishes, return sum.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. It involves a nested loop structure. The outer loop picks an element, and the inner loop iterates through the entire array to count how many times that element appears. If the final count for an element is one, it is considered unique and is added to a running total.

Algorithm Steps:

  • Initialize a variable sum to 0.
  • Loop through the array nums with an index i.
  • For each element nums[i], initialize a counter count to 0.
  • Start a nested loop with an index j to iterate through the array again.
  • If nums[i] is the same as nums[j], increment count.
  • After the inner loop completes, if count is exactly 1, add nums[i] to sum.
  • Once the outer loop is finished, return the total sum.
class Solution {    public int sumOfUnique(int[] nums) {        int sum = 0;        for (int i = 0; i < nums.length; i++) {            int count = 0;            for (int j = 0; j < nums.length; j++) {                if (nums[i] == nums[j]) {                    count++;                }            }            if (count == 1) {                sum += nums[i];            }        }        return sum;    }}

Complexity

Time

O(n^2), where n is the number of elements in `nums`. For each element, we iterate through the entire array again, leading to a quadratic time complexity.

Space

O(1), as we only use a few extra variables to store the sum and count, regardless of the input size.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Requires no additional data structures, resulting in constant space complexity.

Cons

  • Highly inefficient for larger arrays due to the O(n^2) time complexity.

  • Will likely result in a 'Time Limit Exceeded' error on platforms with larger test cases not constrained like this one.

Solutions

class Solution {public  int sumOfUnique(int[] nums) {    int[] cnt = new int[101];    for (int x : nums) {      ++cnt[x];    }    int ans = 0;    for (int x = 0; x < 101; ++x) {      if (cnt[x] == 1) {        ans += x;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem