Code Implementation

class Solution:
    def largestUniqueNumber(self, A):
        from collections import Counter
        count = Counter(A)
        max_unique = -1
        for num in count:
            if count[num] == 1:
                max_unique = max(max_unique, num)
        return max_unique
      

class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        unordered_map<int, int> count;
        for (int num : A) {
            count[num]++;
        }
        int maxUnique = -1;
        for (auto& kv : count) {
            if (kv.second == 1) {
                maxUnique = max(maxUnique, kv.first);
            }
        }
        return maxUnique;
    }
};
      

class Solution {
    public int largestUniqueNumber(int[] A) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : A) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        int maxUnique = -1;
        for (int num : count.keySet()) {
            if (count.get(num) == 1) {
                maxUnique = Math.max(maxUnique, num);
            }
        }
        return maxUnique;
    }
}
      

var largestUniqueNumber = function(A) {
    let count = {};
    for (let num of A) {
        count[num] = (count[num] || 0) + 1;
    }
    let maxUnique = -1;
    for (let num in count) {
        if (count[num] === 1) {
            maxUnique = Math.max(maxUnique, Number(num));
        }
    }
    return maxUnique;
};
      

Problem Description

Given an array of integers A, you are asked to find the largest integer that occurs exactly once in the array. If no such integer exists, return -1.

• Each element in A is an integer. Duplicates may exist.
• If there are multiple unique numbers, you must return the largest one.
• If no number is unique, return -1.
• You cannot reuse elements; only numbers that appear exactly once are considered.

Thought Process

At first glance, you might consider checking every number in the array and seeing if it is unique (occurs only once), keeping track of the largest such number. However, directly checking each number's occurrence by scanning the whole array each time would be inefficient, especially for large arrays.

To improve, you can count the frequency of each number first, then scan through these counts to find the largest number that appears exactly once. This reduces unnecessary repeated checks and leverages efficient data structures for counting.

The main conceptual shift is from brute-force repeated scanning to a two-pass approach: first count, then select.

Solution Approach

To solve this efficiently, follow these steps:

1. Count the occurrences:
   • Use a hash map (dictionary) to count how many times each number appears in A.
   • This allows for O(1) lookups and updates for each number.
2. Find the largest unique number:
   • Iterate through the hash map and check which numbers have a count of exactly one.
   • Keep track of the largest such number seen so far.
   • If no number is unique, return -1.

This method is efficient because it only requires two passes: one to build the count map, and another to determine the answer.

Example Walkthrough

Let's consider the array A = [5, 7, 3, 9, 4, 9, 8, 3, 1].

1. Counting occurrences:
   • 5: 1
   • 7: 1
   • 3: 2
   • 9: 2
   • 4: 1
   • 8: 1
   • 1: 1
2. Finding the largest unique number:
   • Numbers with count 1: 5, 7, 4, 8, 1
   • The largest among these is 8.
3. Return value: 8

Time and Space Complexity

• Brute-force approach:
  • For each number, count its occurrences by scanning the array: O(n^2) time.
  • Space: O(1) extra (not counting input).
• Optimized approach (using hash map):
  • Counting: O(n) time (one pass).
  • Finding largest unique: O(n) time (second pass).
  • Total time: O(n).
  • Space: O(n) for the hash map.

The optimized solution is much faster and handles large inputs efficiently.

Summary

The key insight is to use a hash map to count occurrences, which allows us to efficiently find the largest number that appears exactly once. This approach is both simple and optimal, running in linear time. By separating the counting and selection steps, we avoid redundant work and make the solution both clear and fast.