Teaching Kids Programming – Largest Unique Number via Hash Table, Bucket Sorting and GroupBy Algorithms

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer array nums, return the largest integer that only occurs once. If no integer occurs once, return -1.

Example 1:
Input: nums = [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 is the answer.

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

Constraints:
1 <= nums.length <= 2000
0 <= nums[i] <= 1000

Hints:
Find the number of occurrences of each value.
Use an array or a hash table to do that.
Look for the largest value with number of occurrences = 1.

Largest Unique Number via Hash Table

We can use hash table aka the Counter in Python to count the number of frequencies for each number and then iterating over the keys for the largest unique number.

1
2
3
4
5
6
7
8

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        c = Counter(nums)
        ans = -math.inf
        for k, v in c.items():
            if v == 1 and k > ans:
                ans = k
        return ans if ans != -math.inf else -1

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        c = Counter(nums)
        ans = -math.inf
        for k, v in c.items():
            if v == 1 and k > ans:
                ans = k
        return ans if ans != -math.inf else -1

We can use the max function to compute the max value, however, we have to supply it with a default value if the list is empty i.e. when there are no unique numbers.

1
2
3
4

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        c = Counter(nums)
        return max((k for k,v in c.items() if v == 1), default=-1)

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        c = Counter(nums)
        return max((k for k,v in c.items() if v == 1), default=-1)

Largest Unique Number via Sorting/GroupBy

We can sort the numbers in O(NLogN) – and then use the groupby to group the same numbers, and similarly, we can get the maximum unique value.

1
2
3
4

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:       
        nums.sort()
        return max((k for k, v in groupby(nums) if len(list(v)) == 1), default=-1)

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:       
        nums.sort()
        return max((k for k, v in groupby(nums) if len(list(v)) == 1), default=-1)

Here is a one-liner where we use the sorted iterator.

1
2
3

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:       
        return max((k for k, v in groupby(sorted(nums)) if len(list(v)) == 1), default=-1)

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:       
        return max((k for k, v in groupby(sorted(nums)) if len(list(v)) == 1), default=-1)

The overall time complexity is O(NLogN) due to sorting dominating over the max function.

Largest Unique Number via Bucket Counting

Given the numbers are within a range [0, 1000] we can create 1001 buckets to count the numbers:

1
2
3
4
5
6
7
8
9

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:       
        data = [0] * 1001
        for i in nums:
            data[i] += 1
        for i in range(1000, -1, -1):
            if data[i] == 1:
                return i
        return -1

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:       
        data = [0] * 1001
        for i in nums:
            data[i] += 1
        for i in range(1000, -1, -1):
            if data[i] == 1:
                return i
        return -1

The bucket counting requires iterating over the numbers and thus time complexity is O(N).

Largest Unique Numbers Algorithms/Implementations

• Python Method to Find the Largest Unique Number in an Array
• Teaching Kids Programming – Largest Unique Number via Hash Table, Bucket Sorting and GroupBy Algorithms
• How to Find the Largest Unique Number in Array using Javascript (Functional Programming)
• How to Find the Largest Unique Number in Array (C++)?

–EOF (The Ultimate Computing & Technology Blog) —