Solution Explanation: Largest Unique Number

The problem asks to find the largest integer in an array that appears only once. If no such integer exists, we return -1.

Approach: Counting and Reverse Traversal

This approach leverages the constraint that numbers are within the range [0, 1000]. We can efficiently count the occurrences of each number using a frequency array (or a hash map if the range was significantly larger). After counting, we iterate through the array in reverse order, looking for the first number with a count of 1. This ensures that we find the largest unique number.

Time and Space Complexity Analysis

• Time Complexity: O(n + M), where n is the length of the input array nums and M is the maximum value in nums (1000 in this case). The first loop iterates through nums to count frequencies (O(n)), and the second loop iterates through the frequency array (O(M)). Because M is a constant (1000), the overall time complexity is effectively O(n).

• Space Complexity: O(M). We use an array of size M+1 (or a hash map) to store the frequency counts. Again, since M is a constant, the space complexity is considered O(1) in the context of this problem.

Code Implementation in Multiple Languages

The following code snippets demonstrate the solution in several programming languages. They all follow the same core logic:

1. Counting: Count the occurrences of each number.
2. Reverse Traversal: Iterate from the largest possible number down to 0, returning the first number with a count of 1.
3. Default Return: If no such number is found, return -1.

Python

from collections import Counter
 
class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        counts = Counter(nums)
        for num in sorted(counts, reverse=True):  #Efficiently iterates in descending order
            if counts[num] == 1:
                return num
        return -1
 

Java

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int largestUniqueNumber(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        for (int i = 1000; i >= 0; i--) {
            if (counts.containsKey(i) && counts.get(i) == 1) {
                return i;
            }
        }
        return -1;
    }
}

C++

#include <vector>
#include <map>
 
class Solution {
public:
    int largestUniqueNumber(std::vector<int>& nums) {
        std::map<int, int> counts;
        for (int num : nums) {
            counts[num]++;
        }
        for (int i = 1000; i >= 0; i--) {
            if (counts.count(i) && counts[i] == 1) {
                return i;
            }
        }
        return -1;
    }
};

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var largestUniqueNumber = function(nums) {
    const counts = {};
    for (const num of nums) {
        counts[num] = (counts[num] || 0) + 1;
    }
    for (let i = 1000; i >= 0; i--) {
        if (counts[i] === 1) {
            return i;
        }
    }
    return -1;
};

These examples showcase the flexibility of the approach across different languages. The core logic remains consistent, demonstrating a clear and efficient solution to the problem. Note that the Python solution uses sorted with reverse=True for a more concise way to iterate in descending order. Other languages require explicit loops for this purpose.