1. Sorting

Intuition

After sorting in descending order, we can scan from largest to smallest. A number is unique if it differs from its neighbors. We skip over groups of duplicates and return the first number that appears exactly once.

Algorithm

1. Handle the edge case: if there is only one element, return it.
2. Sort the array in descending order.
3. Iterate through the sorted array:
   • If the current element differs from the next (or is the last element), it is unique. Return it.
   • Otherwise, skip all consecutive duplicates.
4. If no unique number is found, return -1.

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        n = len(nums)

        # If there's only one element, it's unique by default
        if n == 1:
            return nums[0]

        nums.sort(reverse=True)

        # Start from the beginning (largest numbers)
        currentIndex = 0

        while currentIndex < n:
            # If it's the first element or different from the next one, it's unique
            if (
                currentIndex == n - 1
                or nums[currentIndex] != nums[currentIndex + 1]
            ):
                return nums[currentIndex]
            # Skip duplicates
            while (
                currentIndex < n - 1
                and nums[currentIndex] == nums[currentIndex + 1]
            ):
                currentIndex += 1
            # Move to the next unique number
            currentIndex += 1

        return -1

Time & Space Complexity

• Time complexity: $O(n \cdot \log n)$
• Space complexity: $O(S)$ Depends on the language of implementation

Where $n$ is the length of the nums array and $S$ is the sorting algorthm

---

2. Sorted Map

Intuition

We can count the frequency of each number using a sorted map (tree map). Since the map maintains keys in sorted order, we iterate from the largest key downward and return the first key with frequency 1.

Algorithm

1. Build a frequency map counting occurrences of each number.
2. Use a sorted map structure that keeps keys in order.
3. Iterate through the keys in descending order.
4. Return the first key with a frequency of 1, or -1 if none exists.

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        # Create a frequency map
        frequency_map = {}
        for num in nums:
            frequency_map[num] = frequency_map.get(num, 0) + 1

        # Create a sorted OrderedDict
        sorted_map = OrderedDict(sorted(frequency_map.items(), reverse=True))

        # Find the largest unique number
        for num, freq in sorted_map.items():
            if freq == 1:
                return num

        return -1

Time & Space Complexity

• Time complexity: $O(n \cdot \log n)$
• Space complexity: $O(n)$

Where $n$ is the length of the nums array.

---

3. Map

Intuition

Using a regular hash map, we count frequencies in linear time. Then we scan all entries and track the maximum number with frequency 1. This avoids the overhead of maintaining sorted order.

Algorithm

1. Build a frequency map counting occurrences of each number.
2. Initialize the result to -1.
3. Iterate through all entries in the map:
   • If frequency equals 1 and the number is larger than the current result, update the result.
4. Return the result.

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        # Use Counter to count frequencies of numbers
        frequency_map = Counter(nums)

        # Find the largest number with frequency 1, or -1 if none found
        return max(
            (num for num, freq in frequency_map.items() if freq == 1),
            default=-1,
        )

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of the nums array.

---

Common Pitfalls

Returning the First Unique Instead of the Largest

When iterating through numbers, it is tempting to return immediately upon finding a unique number. However, the problem asks for the largest unique number. Without sorting or tracking the maximum, returning early may yield a smaller unique value when a larger one exists.

Confusing Unique with Distinct

A number is unique if it appears exactly once in the array, not if it is different from its neighbors. Using logic that checks for distinct consecutive elements after sorting misses duplicates that are separated by other values in the original array.