Jobs

Interviews

Discussions

Majority Element II

Medium

Asked by:

15 views

Topics:

Arrays

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

1 <= nums.length <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹

Follow up: Could you solve the problem in linear time and in O(1) space?

Majority Element II

Medium

Asked by:

15 views

Topics:

Arrays

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

1 <= nums.length <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹

Follow up: Could you solve the problem in linear time and in O(1) space?

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 expected range of integer values within the `nums` array? Can they be negative, zero, or only positive?
What should I return if there are no elements that appear more than ⌊ n / 3 ⌋ times? Should I return an empty list?
If multiple elements satisfy the condition, is the order of elements in the returned list significant, or can they be in any order?
Is it possible for the input array `nums` to be null or empty? If so, what should I return in those cases?
Does the input array contain only integers, or could it potentially contain other data types?

Brute Force Solution

Approach

The brute force approach to finding majority elements involves systematically checking each possible element to see if it appears more than a certain threshold. We essentially count the occurrences of every element and compare the count to the specified limit. It's like manually tallying votes for each candidate to see if anyone wins by a wide margin.

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

Take the first number in the group.
Go through the entire group and count how many times that first number appears.
Check if that count is more than one-third the size of the entire group. If it is, remember that number.
Now, take the second number in the group.
Again, go through the entire group and count how many times this second number appears.
Check if this count is more than one-third the size of the group. If it is, and it's different from the first number you remembered, then remember this number as well.
Continue this process for every number in the group.
At the end, you will have a list of numbers that each appear more than one-third of the time.

Code Implementation

def majority_element_brute_force(numbers):
    majority_elements = []
    minimum_majority_count = len(numbers) // 3

    for possible_majority_element_index in range(len(numbers)):
        possible_majority_element = numbers[possible_majority_element_index]
        element_count = 0

        for number_index in range(len(numbers)):
            if numbers[number_index] == possible_majority_element:
                element_count += 1

        # Need to determine if element is the majority

        if element_count > minimum_majority_count:

            is_duplicate = False
            for already_found_element in majority_elements:
                if already_found_element == possible_majority_element:
                    is_duplicate = True
                    break

            # Avoid duplicates in the result

            if not is_duplicate:

                majority_elements.append(possible_majority_element)

    return majority_elements

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The described brute force algorithm iterates through each of the n elements in the input array. For each of these n elements, it then iterates through the entire array again to count the occurrences of that particular element. This nested loop structure means that for each element, we perform n comparisons. Therefore, the total number of operations scales proportionally to n * n, making the time complexity O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through the input array and counts the occurrences of each element. It only stores a few variables: the current element being checked and its count. The number of such variables remains constant regardless of the size N of the input array. Therefore, the space complexity is constant.

Optimal Solution

Approach

The problem requires us to find numbers that appear more than a third of the time in a list. The clever trick here is to realize that there can be at most two such numbers. We'll use a voting-based approach to identify potential candidates and then verify their counts.

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

Imagine you're running an election, but you only care about the top two candidates.
Go through the list of numbers, and keep track of at most two candidates and their vote counts.
If you find a number matching one of your candidates, increase that candidate's vote count.
If you find a new number and have space (a candidate with zero votes), make it a new candidate and give it a vote.
If you find a new number and have no space, decrease the vote count of both your candidates.
After processing all numbers, you have two potential candidates. Now, count how many times each of them actually appears in the original list.
Finally, report the numbers that appear more than a third of the time, based on the actual counts.

Code Implementation

def majorityElement(numbers):
    candidate1 = None
    candidate2 = None
    candidate1_votes = 0
    candidate2_votes = 0

    for number in numbers:
        if number == candidate1:
            candidate1_votes += 1
        elif number == candidate2:
            candidate2_votes += 1
        elif candidate1_votes == 0:
            # Assign the number as a new candidate.
            candidate1 = number
            candidate1_votes = 1

        elif candidate2_votes == 0:
            # Assign the number as a new candidate.
            candidate2 = number
            candidate2_votes = 1
        else:
            # Decrement votes of both candidates.
            candidate1_votes -= 1
            candidate2_votes -= 1

    actual_count1 = 0
    actual_count2 = 0

    for number in numbers:
        if number == candidate1:
            actual_count1 += 1
        if number == candidate2:
            actual_count2 += 1

    result = []
    if actual_count1 > len(numbers) // 3:
        # Verify candidate1's occurence.
        result.append(candidate1)

    if candidate1 != candidate2 and actual_count2 > len(numbers) // 3:
        # Verify candidate2's occurence.
        result.append(candidate2)

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list nums of size n to identify potential candidates for majority elements, which takes O(n) time. Subsequently, it iterates through the list again, at most twice, to verify the counts of these candidates, which also takes O(n) time. Therefore, the overall time complexity is dominated by these linear traversals, resulting in O(n).

Space Complexity

O(1) – The algorithm maintains a constant number of variables: two to store the potential candidates and two to store their respective counts. These variables do not depend on the size of the input list (N). The algorithm does not utilize any auxiliary data structures such as lists, hash maps, or recursion. Therefore, the auxiliary space used is constant, regardless of the input size N.

Edge Cases

Case	How to Handle
Empty input array	Return an empty list because no elements can appear more than n/3 times.
Array with one element	Return the single element as it appears more than n/3 (which is 0) times.
Array with two elements, both identical	Return the single element, as it appears twice, which is more than n/3 (2/3 which truncates to 0).
Array with two elements, both distinct	Return an empty list since neither element appears more than n/3 (0) times.
Array with all elements identical	Return the single unique element, as it is the majority element.
Large array with extreme positive and negative values	Moyer's Voting Algorithm handles both large positive and negative values without integer overflow assuming the counts are stored in a data type that can accomodate the array size.
Array with elements clustered around a few values but no strict majority	Moyer's Voting Algorithm finds candidates, and a final validation step checks if their counts exceed n/3.
Array containing zeros	The algorithm should correctly count zeros like any other integer element.

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 expected range of integer values within the `nums` array? Can they be negative, zero, or only positive?
What should I return if there are no elements that appear more than ⌊ n / 3 ⌋ times? Should I return an empty list?
If multiple elements satisfy the condition, is the order of elements in the returned list significant, or can they be in any order?
Is it possible for the input array `nums` to be null or empty? If so, what should I return in those cases?
Does the input array contain only integers, or could it potentially contain other data types?

Brute Force Solution

Approach

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

Take the first number in the group.
Go through the entire group and count how many times that first number appears.
Check if that count is more than one-third the size of the entire group. If it is, remember that number.
Now, take the second number in the group.
Again, go through the entire group and count how many times this second number appears.
Check if this count is more than one-third the size of the group. If it is, and it's different from the first number you remembered, then remember this number as well.
Continue this process for every number in the group.
At the end, you will have a list of numbers that each appear more than one-third of the time.

Code Implementation

def majority_element_brute_force(numbers):
    majority_elements = []
    minimum_majority_count = len(numbers) // 3

    for possible_majority_element_index in range(len(numbers)):
        possible_majority_element = numbers[possible_majority_element_index]
        element_count = 0

        for number_index in range(len(numbers)):
            if numbers[number_index] == possible_majority_element:
                element_count += 1

        # Need to determine if element is the majority

        if element_count > minimum_majority_count:

            is_duplicate = False
            for already_found_element in majority_elements:
                if already_found_element == possible_majority_element:
                    is_duplicate = True
                    break

            # Avoid duplicates in the result

            if not is_duplicate:

                majority_elements.append(possible_majority_element)

    return majority_elements

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you're running an election, but you only care about the top two candidates.
Go through the list of numbers, and keep track of at most two candidates and their vote counts.
If you find a number matching one of your candidates, increase that candidate's vote count.
If you find a new number and have space (a candidate with zero votes), make it a new candidate and give it a vote.
If you find a new number and have no space, decrease the vote count of both your candidates.
After processing all numbers, you have two potential candidates. Now, count how many times each of them actually appears in the original list.
Finally, report the numbers that appear more than a third of the time, based on the actual counts.

Code Implementation

def majorityElement(numbers):
    candidate1 = None
    candidate2 = None
    candidate1_votes = 0
    candidate2_votes = 0

    for number in numbers:
        if number == candidate1:
            candidate1_votes += 1
        elif number == candidate2:
            candidate2_votes += 1
        elif candidate1_votes == 0:
            # Assign the number as a new candidate.
            candidate1 = number
            candidate1_votes = 1

        elif candidate2_votes == 0:
            # Assign the number as a new candidate.
            candidate2 = number
            candidate2_votes = 1
        else:
            # Decrement votes of both candidates.
            candidate1_votes -= 1
            candidate2_votes -= 1

    actual_count1 = 0
    actual_count2 = 0

    for number in numbers:
        if number == candidate1:
            actual_count1 += 1
        if number == candidate2:
            actual_count2 += 1

    result = []
    if actual_count1 > len(numbers) // 3:
        # Verify candidate1's occurence.
        result.append(candidate1)

    if candidate1 != candidate2 and actual_count2 > len(numbers) // 3:
        # Verify candidate2's occurence.
        result.append(candidate2)

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty list because no elements can appear more than n/3 times.
Array with one element	Return the single element as it appears more than n/3 (which is 0) times.
Array with two elements, both identical	Return the single element, as it appears twice, which is more than n/3 (2/3 which truncates to 0).
Array with two elements, both distinct	Return an empty list since neither element appears more than n/3 (0) times.
Array with all elements identical	Return the single unique element, as it is the majority element.
Large array with extreme positive and negative values	Moyer's Voting Algorithm handles both large positive and negative values without integer overflow assuming the counts are stored in a data type that can accomodate the array size.
Array with elements clustered around a few values but no strict majority	Moyer's Voting Algorithm finds candidates, and a final validation step checks if their counts exceed n/3.
Array containing zeros	The algorithm should correctly count zeros like any other integer element.