# Largest Unique Number

Given an array of integers `A`, return the largest integer that only occurs once. If no integer occurs once, return -1.

Example 1:

```Input: [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation:
The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it's the answer.```

Example 2:

```Input: [9,9,8,8]
Output: -1
Explanation:
There is no number that occurs only once.```

Note:

1. `1 <= A.length <= 2000`
2. `0 <= A[i] <= 1000`

Intuition

Here we can use a `HashMap` to store the count of each number. Since hash maps are unordered we need to traverse it to find out if the count of the current element is 1. If it is, it is a candidate for our answer. We take the maximum of these candidates and return it as the result.

Algorithm

1. Create a `HashMap` that stores the count of each number.
2. Iterate over the sequence of numbers and populate the map with the count of each number.
3. Initialize the `result` as `-1`.
4. Iterate over the map and if the `value` of the `key` is `1`, set `result` equal to the maximum of `key` or the current `result`.
5. Return the result at the end.
```class Solution {
public int largestUniqueNumber(int[] A) {
Map<Integer, Integer> count = new HashMap<Integer, Integer>();
// Store counts of each element
for (int i : A) {
count.put(i, count.getOrDefault(i, 0) + 1);
}
int result = -1;
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
// If count of the integer is 1 get maximum.
if (entry.getValue() == 1) {
result = Math.max(result, entry.getKey());
}
}
return result;
}
}
```

Complexity Analysis

• Time Complexity: `O(n)`. Where n is the length of the array. This is because we must insert every number into the hash map and insertion into a hash map is a constant time operation.
• Space Complexity: `O(n)`. In the worst case we will need to store all of the numbers with a frequency of `1`.

Categories: Map

Tagged as: