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:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s