First Unique Number

Medium

Asked by:

9 views

Topics:

Arrays

You are given an array of integers votes where each integer represents the number of votes a candidate received. We need to rank the candidates by the number of votes they received from highest to lowest.

Return a string of all the candidates sorted by the number of votes they received. If two or more candidates receive the same number of votes, then order them alphabetically. For example, if votes = ["ABC", "ACB", "ABC", "ACB", "ACB"] then candidate A received 5 votes, candidate B received 2 votes, and candidate C received 3 votes.

The solution should be alphabetically ordered string. For example, if votes = ["ABC", "ACB", "ABC", "ACB", "ACB"] then return "ACB". If votes = ["WXYZ","XYZW"] then return "XWYZ".

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: 
Candidate A receives 5 votes.
Candidate B receives 2 votes.
Candidate C receives 3 votes.
The order is ACB.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: 
Candidate W receives 1 vote.
Candidate X receives 1 vote.
Candidate Y receives 1 vote.
Candidate Z receives 1 vote.
The order is ordered alphabetically: WXYZ.
In the end, we need to sort them according to the number of votes they received.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: 
Only one round of votes.
The order is ZMNAGUEDSJYLBOPHRQICWFXTVK.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
All characters of votes[i] are upper-case English letters.
votes[i] are distinct.

Try coding it in LeetCode

First Unique Number

Medium

Asked by:

9 views

Topics:

Arrays

You are given an array of integers votes where each integer represents the number of votes a candidate received. We need to rank the candidates by the number of votes they received from highest to lowest.

Return a string of all the candidates sorted by the number of votes they received. If two or more candidates receive the same number of votes, then order them alphabetically. For example, if votes = ["ABC", "ACB", "ABC", "ACB", "ACB"] then candidate A received 5 votes, candidate B received 2 votes, and candidate C received 3 votes.

The solution should be alphabetically ordered string. For example, if votes = ["ABC", "ACB", "ABC", "ACB", "ACB"] then return "ACB". If votes = ["WXYZ","XYZW"] then return "XWYZ".

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: 
Candidate A receives 5 votes.
Candidate B receives 2 votes.
Candidate C receives 3 votes.
The order is ACB.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: 
Candidate W receives 1 vote.
Candidate X receives 1 vote.
Candidate Y receives 1 vote.
Candidate Z receives 1 vote.
The order is ordered alphabetically: WXYZ.
In the end, we need to sort them according to the number of votes they received.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: 
Only one round of votes.
The order is ZMNAGUEDSJYLBOPHRQICWFXTVK.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
All characters of votes[i] are upper-case English letters.
votes[i] are distinct.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array? Can I expect negative numbers, zeros, or extremely large positive numbers?
What should I return if the input array `nums` is empty or null?
If there are multiple unique integers in the array, is the 'first' one defined by its index in the original array?
Are there any memory constraints I should be aware of, given a potentially large input array?
Can you provide a few example input arrays and their corresponding expected outputs to ensure my understanding is correct?

Brute Force Solution

Approach

The brute force approach for finding the first unique number involves checking each number to see if it is unique. We accomplish this by comparing each number with every other number in the list. The process continues until a unique number is discovered or all numbers have been examined.

Here's how the algorithm would work step-by-step:

Start with the first number in the list.
Compare this number to every other number in the list.
If you find another number that's the same, then the first number is not unique, so move to the next number in the list.
If you compare the first number to all other numbers and don't find a match, then it's unique, and you've found your answer.
Repeat this process with the second number, then the third, and so on, until you find a unique number.
If you reach the end of the list without finding a unique number, it means there are no unique numbers in the list.

Code Implementation

def find_first_unique_number_brute_force(number_list):
    for current_index in range(len(number_list)):
        is_unique = True

        # Compare the current number to all other numbers
        for comparison_index in range(len(number_list)):

            # Skip comparing the number to itself
            if current_index == comparison_index:
                continue

            if number_list[current_index] == number_list[comparison_index]:
                # If a match is found, the number is not unique
                is_unique = False

                break

        # If the number is unique, return it
        if is_unique:

            return number_list[current_index]

    # If no unique number is found, return None
    return None

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through the input array of size n. For each element, it compares it with every other element in the array to check for uniqueness. This involves a nested loop structure where the outer loop iterates n times and the inner loop, in the worst case, iterates up to n times for each outer loop iteration. Therefore, the total number of comparisons approximates n * n, resulting in a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach, as described, only iterates through the input list and compares elements directly. It doesn't create any additional data structures like temporary lists, hash maps, or sets to store intermediate results or frequency counts. Only a few variables are used for indexing and comparison, irrespective of the input size N. Therefore, the auxiliary space used is constant and does not depend on the size of the input list.

Optimal Solution

Approach

The best way to find the first unique number is to keep track of how many times we've seen each number. We can update these counts as we look at the list, and also keep track of the numbers in the order we saw them.

Here's how the algorithm would work step-by-step:

As you process the list of numbers, keep a record of how many times each number appears.
Also, maintain the order of numbers as you encounter them.
When someone asks for the first unique number, go through the list of numbers in the order you saw them.
Check if the number only appeared once, according to your count record.
If you find a number that appeared only once, that's your answer.
If you go through the whole list and don't find a unique number, it means there isn't one.

Code Implementation

class FirstUnique:
    def __init__(self, numbers):
        self.number_counts = {}
        self.number_queue = []
        for number in numbers:
            self.add(number)

    def showFirstUnique(self):
        # Iterate to find the first unique number
        while self.number_queue and self.number_counts[self.number_queue[0]] > 1:
            self.number_queue.pop(0)
        
        if self.number_queue:
            return self.number_queue[0]
        else:
            return -1

    def add(self, number):
        # Increment the count for the number.
        if number in self.number_counts:
            self.number_counts[number] += 1
        else:
            self.number_counts[number] = 1
            # Only add to queue if seen for the first time
            self.number_queue.append(number)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of n numbers to count the frequency of each number, which takes O(n) time. Then, when asked for the first unique number, it iterates through the original list of n numbers again. In this second pass, for each number, it looks up its count, which is assumed to be an O(1) operation (e.g., using a hash map for counting). Therefore, the second pass also takes O(n) time. The overall time complexity is thus O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses a hash map (or count record) to store the frequency of each number encountered, potentially storing up to N unique numbers where N is the number of elements in the input list. Additionally, it maintains the order of numbers encountered in a list, which can also grow up to size N in the worst case if all numbers are unique. Therefore, the auxiliary space used grows linearly with the input size N. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return -1 immediately as there are no elements to check.
Input array with one element	Check if the single element's count is one, returning it, otherwise -1.
Input array with all identical elements	The counts of all elements will be greater than 1, so return -1.
Large input array with a single unique element at the very end	The solution should iterate through the entire array efficiently, not timing out or using excessive memory.
Input array contains both positive and negative numbers, including zero	The counting mechanism (e.g., hash map) must correctly handle non-positive numbers.
Input array contains duplicate numbers with one unique number	The count of the unique number will be equal to one while the others are greater than one.
Input array with maximum integer values that lead to overflow if summed directly	The solution should not sum the array elements directly, and the counts should be stored in a data structure that doesn't cause an overflow (e.g., long).
All elements in the input appear an even number of times	Return -1 when iteration is complete because no numbers have a count of one.