Jobs

Interviews

Discussions

Majority Element II

Medium

Majority Element II

Medium

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 within the integer array `nums`?
What should I return if the input array is null or empty?
If multiple elements satisfy the condition of appearing more than ⌊ n/3 ⌋ times, in what order should I return them?
Are duplicate values allowed in the input array, and if so, should I count them individually when determining if an element appears more than ⌊ n/3 ⌋ times?
Is it possible for an element to appear exactly ⌊ n/3 ⌋ times? If so, should that element be included in the result?

Brute Force Solution

Approach

The goal is to find numbers that appear more than a third of the time in a collection. The brute force way is to simply count how many times each number appears and then check if that count is large enough.

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

Take the first number in the collection.
Go through the entire collection and count how many times that first number appears.
See if that count is greater than one-third of the total number of items in the collection. If so, remember this number.
Now, take the second number in the collection.
Again, go through the entire collection and count how many times this second number appears.
See if this second number's count is also greater than one-third of the total. If so, and if it's not the same as the first number you remembered, remember this number too.
Keep doing this for every number in the collection, one by one.
At the end, you will have a list of all the numbers that appeared more than one-third of the time.

Code Implementation

def majority_element_brute_force(numbers):
    number_of_elements = len(numbers)
    required_frequency = number_of_elements // 3
    result = []

    for first_number_index in range(number_of_elements):
        current_number = numbers[first_number_index]
        frequency = 0

        for second_number_index in range(number_of_elements):
            if numbers[second_number_index] == current_number:
                frequency += 1

        # Check if the frequency exceeds the threshold
        if frequency > required_frequency:
            # Prevent duplicates in result
            if current_number not in result:

                #Storing only if the number appears more than n/3 times
                result.append(current_number)

    return result

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input array. For each element, it then iterates through the entire array again to count its occurrences. This results in a nested loop structure where the inner loop runs n times for each of the n iterations of the outer loop. Therefore, the total number of operations is proportional to n * n, which gives a time complexity of O(n²).

Space Complexity

O(1) – The provided plain English explanation iterates through the input array and counts the occurrences of each element. It remembers at most two numbers that satisfy the condition of appearing more than one-third of the time. These remembered numbers are stored in a fixed number of variables, independent of the input size N. Therefore, the auxiliary space used is constant regardless of the size of the input array, N.

Optimal Solution

Approach

The problem asks us to find numbers that appear more than a third of the time in a collection. Instead of counting each number individually, we can use a clever method to track potential candidates, greatly reducing the number of counts needed. This eliminates the need to check counts for everything.

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

We'll keep track of at most two candidate numbers and their counts.
Go through each number in the collection. If a number matches one of the candidates, increase that candidate's count.
If a number doesn't match any candidate, check if either candidate's count is zero. If so, replace that candidate with the current number and set its count to one.
If both candidates are already in use, decrease the counts of both candidates by one.
After going through the entire collection, we'll have at most two potential majority elements. However, we still need to verify they are actually majority elements.
Go through the original collection again and count how many times each of the potential candidates actually appears.
Finally, check if the count for each candidate is greater than one-third of the size of the collection. If so, that number is a majority element.

Code Implementation

def majorityElement(numbers):
    candidate1 = None
    candidate2 = None
    candidate1_count = 0
    candidate2_count = 0
    length_of_numbers = len(numbers)

    for number in numbers:
        if number == candidate1:
            candidate1_count += 1
        elif number == candidate2:
            candidate2_count += 1
        elif candidate1_count == 0:
            # Assign the current number if candidate1 is empty
            candidate1 = number
            candidate1_count = 1

        elif candidate2_count == 0:
            # Assign the current number if candidate2 is empty
            candidate2 = number
            candidate2_count = 1

        else:
            # Decrement counts if no candidate matches
            candidate1_count -= 1
            candidate2_count -= 1

    candidate1_actual_count = 0
    candidate2_actual_count = 0

    for number in numbers:
        if number == candidate1:
            candidate1_actual_count += 1
        if number == candidate2:
            candidate2_actual_count += 1

    result = []
    if candidate1_actual_count > length_of_numbers // 3:
        # Add the first candidate if it's a majority element
        result.append(candidate1)

    if candidate2_actual_count > length_of_numbers // 3 and candidate1 != candidate2:
        # Ensure we don't add duplicates when candidates are same
        result.append(candidate2)

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array (of size n) twice. The first iteration identifies potential candidates for majority elements. The second iteration counts the occurrences of these candidates to verify if they appear more than n/3 times. Both iterations are linear, resulting in a time complexity of O(n) + O(n) which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a fixed number of integer variables to store the two candidate numbers and their respective counts. No auxiliary data structures like lists, arrays, or hash maps are created that scale with the input size N (the number of elements in the input collection). The space used is therefore constant regardless of the size of the input.

Edge Cases

Case	How to Handle
Empty input array	Return an empty list as there can be no majority elements in an empty array.
Input array with one element	Return the single element in a list as it appears more than n/3 times.
Input array with two elements	Check if each element appears more than n/3 (which is 0 in this case) and return the elements that do.
Array with all identical elements	Return the single element as it appears n times, which is always greater than n/3.
Array with a single element appearing more than n/3 times, and the rest appearing less	Moor's voting algorithm or a hash map will correctly identify and return that element.
Array with two elements appearing more than n/3 times	Moor's voting algorithm (with two candidates) or a hash map will correctly identify and return both elements.
Array with negative numbers, zeros, and positive numbers	The chosen algorithm (Moor's or hash map) should handle different number types without specific modifications.
Integer overflow if calculating counts naively	Avoid naive count incrementing by using the optimized Moor's voting algorithm to prevent overflow during count calculations.

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 within the integer array `nums`?
What should I return if the input array is null or empty?
If multiple elements satisfy the condition of appearing more than ⌊ n/3 ⌋ times, in what order should I return them?
Are duplicate values allowed in the input array, and if so, should I count them individually when determining if an element appears more than ⌊ n/3 ⌋ times?
Is it possible for an element to appear exactly ⌊ n/3 ⌋ times? If so, should that element be included in the result?

Brute Force Solution

Approach

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

Take the first number in the collection.
Go through the entire collection and count how many times that first number appears.
See if that count is greater than one-third of the total number of items in the collection. If so, remember this number.
Now, take the second number in the collection.
Again, go through the entire collection and count how many times this second number appears.
See if this second number's count is also greater than one-third of the total. If so, and if it's not the same as the first number you remembered, remember this number too.
Keep doing this for every number in the collection, one by one.
At the end, you will have a list of all the numbers that appeared more than one-third of the time.

Code Implementation

def majority_element_brute_force(numbers):
    number_of_elements = len(numbers)
    required_frequency = number_of_elements // 3
    result = []

    for first_number_index in range(number_of_elements):
        current_number = numbers[first_number_index]
        frequency = 0

        for second_number_index in range(number_of_elements):
            if numbers[second_number_index] == current_number:
                frequency += 1

        # Check if the frequency exceeds the threshold
        if frequency > required_frequency:
            # Prevent duplicates in result
            if current_number not in result:

                #Storing only if the number appears more than n/3 times
                result.append(current_number)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

We'll keep track of at most two candidate numbers and their counts.
Go through each number in the collection. If a number matches one of the candidates, increase that candidate's count.
If a number doesn't match any candidate, check if either candidate's count is zero. If so, replace that candidate with the current number and set its count to one.
If both candidates are already in use, decrease the counts of both candidates by one.
After going through the entire collection, we'll have at most two potential majority elements. However, we still need to verify they are actually majority elements.
Go through the original collection again and count how many times each of the potential candidates actually appears.
Finally, check if the count for each candidate is greater than one-third of the size of the collection. If so, that number is a majority element.

Code Implementation

def majorityElement(numbers):
    candidate1 = None
    candidate2 = None
    candidate1_count = 0
    candidate2_count = 0
    length_of_numbers = len(numbers)

    for number in numbers:
        if number == candidate1:
            candidate1_count += 1
        elif number == candidate2:
            candidate2_count += 1
        elif candidate1_count == 0:
            # Assign the current number if candidate1 is empty
            candidate1 = number
            candidate1_count = 1

        elif candidate2_count == 0:
            # Assign the current number if candidate2 is empty
            candidate2 = number
            candidate2_count = 1

        else:
            # Decrement counts if no candidate matches
            candidate1_count -= 1
            candidate2_count -= 1

    candidate1_actual_count = 0
    candidate2_actual_count = 0

    for number in numbers:
        if number == candidate1:
            candidate1_actual_count += 1
        if number == candidate2:
            candidate2_actual_count += 1

    result = []
    if candidate1_actual_count > length_of_numbers // 3:
        # Add the first candidate if it's a majority element
        result.append(candidate1)

    if candidate2_actual_count > length_of_numbers // 3 and candidate1 != candidate2:
        # Ensure we don't add duplicates when candidates are same
        result.append(candidate2)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty list as there can be no majority elements in an empty array.
Input array with one element	Return the single element in a list as it appears more than n/3 times.
Input array with two elements	Check if each element appears more than n/3 (which is 0 in this case) and return the elements that do.
Array with all identical elements	Return the single element as it appears n times, which is always greater than n/3.
Array with a single element appearing more than n/3 times, and the rest appearing less	Moor's voting algorithm or a hash map will correctly identify and return that element.
Array with two elements appearing more than n/3 times	Moor's voting algorithm (with two candidates) or a hash map will correctly identify and return both elements.
Array with negative numbers, zeros, and positive numbers	The chosen algorithm (Moor's or hash map) should handle different number types without specific modifications.
Integer overflow if calculating counts naively	Avoid naive count incrementing by using the optimized Moor's voting algorithm to prevent overflow during count calculations.