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 1:
1Input: nums = [1,2,3,2]
2Output: 4
3Explanation: The unique elements are [1,3], and the sum is 4.
Example 2:
1Input: nums = [1,1,1,1,1]
2Output: 0
3Explanation: There are no unique elements, and the sum is 0.
Example 3:
1Input: nums = [1,2,3,4,5]
2Output: 15
3Explanation: The unique elements are [1,2,3,4,5], and the sum is 15.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100
Solution
This problem states that each number n nums is between 1 (inclusive) and 101 (exclusive). Also, the problem constraint states that nums is never an empty array.
Brute Force approach
The brute force approach would iterate through all elements of the array nums and check if they exists second time in the array. If yes, ignore else add it to sum variable. This approach is not optimal as it has time complexity of O(n^2).
1class Solution {
2 public int sumOfUnique (int[] nums) {
3 int sum = 0;
4 for (int i = 0; i < nums.length; i++) {
5 boolean isUnique = true;
6 for (int j = 0; j < nums.length; j++) {
7 if (i != j && nums[i] == nums[j]) {
8 isUnique = false;
9 break;
10 }
11 }
12 if (isUnique)
13 sum += nums[i];
14 }
15 return sum;
16 }
17}
- Time Complexity:
O(n^2) - Space Complexity:
O(1)
Using Array
In this case, we have only 100 unique numbers which we can easily accommodate in an array. We can use their respective indices to track the frequency of the number. Once we have populated this frequency array. We have to iterate through it and make sure that we add only those numbers whose frequency is exactly 1 to the sum variable. Finally, we return this sum variable.
1class Solution {
2 public int sumOfUnique(int[] nums) {
3 int[] frequency = new int[101];
4 int sum = 0;
5 for (int i = 0; i < nums.length; i++) {
6 frequency[nums[i]]++;
7 }
8 for (int i = 0; i < frequency.length; i++) {
9 if (frequency[i] == 1)
10 sum += i;
11 }
12 return sum;
13 }
14}
- Time Complexity: The reading through array is constant time, however, there are two loops. So, it takes at least
O(n)time complexity - Space Complexity: We are creating an array of fixed size 101 which means space complexity is constant
O(1).
Using Hashing
Another approach to solve the problem is to track the existence of each number in Hash data structure. First, we iterate through nums array to fill this HashMap frequencyMap with each number’s frequency. For every new number, we add it to the map and if we see the number again, we update the frequency. Next, iterate through this map and sum all elements whose frequency is 1.
You might think HashSet might work. In that case, our code would look something like this.
1 public int sumOfUnique (int[] nums) {
2 Set<Integer> unique = new HashSet<>();
3 for (int num : nums) {
4 if (!unique.contains(num))
5 unique.add(num);
6 else
7 unique.remove(num);
8 }
9 int sum = 0;
10 for (int num : unique) {
11 sum += num;
12 }
13 return sum;
14 }
However, with this approach, we might end up giving incorrect results for inputs like [1, 1, 1, 1, 1] because in this case, we will add and remove correctly as long as number is repeated even number of times. However, in this case, it’s odd and at the last iteration, we will not have this number 1 present in the HashSet and we will add it incorrectly when it should have been ignored. So, we need HashMap.
1class Solution {
2 public int sumOfUnique (int[] nums) {
3 Map<Integer, Integer> frequencyMap = new HashMap<>();
4 for (int num : nums) {
5 frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
6 }
7 int sum = 0;
8 for (int num : frequencyMap.keySet()) {
9 sum += frequencyMap.get(num) == 1 ? num : 0;
10 }
11 return sum;
12 }
13}
- Time Complexity:
O(n) - Space Complexity: In worst case, it can have upto 100 key-value pairs, so
O(1).
Comments