Jobs

Interviews

Discussions

Majority Element

Easy

Google

1 view

Topics:

Arrays

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

For example:

nums = [3,2,3] should return 3
nums = [2,2,1,1,1,2,2] should return 2

Write a function to find the majority element in an array. The function should be efficient and handle various input arrays, including cases where all elements are the same, and the array has only one element. What is the time and space complexity of your solution? Can you implement this in O(n) time and O(1) space?

Majority Element

Easy

Google

1 view

Topics:

Arrays

For example:

nums = [3,2,3] should return 3
nums = [2,2,1,1,1,2,2] should return 2

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 should I return if no majority element exists?
What is the data type of the numbers in the array, and are negative numbers allowed?
Is the array guaranteed to be non-empty?
By 'majority element', do you mean an element that appears strictly more than n/2 times, where n is the size of the array?
How large can the input array be?

Brute Force Solution

Approach

The problem asks us to find the element that appears more than half the time in a collection of elements. The brute force method involves counting how many times each element appears in the entire collection, one by one, to see if it's the majority element.

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

Take the first element from the collection.
Go through the entire collection and count how many times this element appears.
Check if the count is more than half the size of the entire collection. If it is, then we've found our majority element, and we're done.
If the first element is not the majority element, move on to the second element in the collection.
Repeat the counting process for the second element, then the third, and so on, until we find an element that appears more than half the time.
If we reach the end of the collection without finding an element that meets the condition, then there is no majority element.

Code Implementation

def find_majority_element_brute_force(elements):
    collection_size = len(elements)

    for i in range(collection_size):
        current_element = elements[i]
        element_count = 0

        # Count the frequency of the current element
        for j in range(collection_size):
            if elements[j] == current_element:
                element_count += 1

        # Check if current element is the majority
        if element_count > collection_size / 2:
            return current_element

    # No majority element found
    return None

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each element in the input array of size n. For each element, it then iterates through the entire array again to count its occurrences. Thus, for each of the n elements, we perform a count operation that takes O(n) time. This results in a nested loop structure where the outer loop iterates n times and the inner loop iterates n times for each outer loop iteration. Therefore, the total number of operations is proportional to n * n, giving a time complexity of O(n²).

Space Complexity

O(1) – The provided brute force algorithm iterates through the collection of elements and counts the occurrences of each element. It doesn't create any auxiliary data structures like lists, hash maps, or arrays to store intermediate results. The only additional memory used is for a few variables, such as a counter and an index, and these require a constant amount of space regardless of the input size N, where N is the number of elements in the collection. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The challenge is to find the number that appears more than half the time in a list. The optimal approach leverages a clever trick where we keep track of a 'candidate' number and a counter, effectively canceling out elements that aren't the majority.

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

Pick a candidate number from the list and set its count to 1.
Go through the rest of the list. If the current number is the same as the candidate, increase the count. If it's different, decrease the count.
If the count drops to zero, it means the current candidate is unlikely to be the majority element. Pick the current number in the list as the new candidate and reset the count to 1.
After going through the whole list, you'll have a potential candidate. This candidate is the most likely majority element.
To be sure, count how many times the potential candidate appears in the original list.
If it appears more than half the time, it's the majority element. Otherwise, there is no majority element.

Code Implementation

def find_majority_element(number_list):
    candidate_element = None
    candidate_count = 0

    for number in number_list:
        if candidate_count == 0:
            # If count is 0, assign current number as candidate.
            candidate_element = number
            candidate_count = 1

        elif candidate_element == number:
            candidate_count += 1

        else:
            candidate_count -= 1

    # Verify the candidate is indeed the majority element.
    candidate_frequency = number_list.count(candidate_element)

    if candidate_frequency > len(number_list) // 2:
        return candidate_element
    else:
        # No majority element exists
        return None

Big(O) Analysis

Time Complexity

O(n) – The algorithm first iterates through the input list of size n to find a potential majority element using the Boyer-Moore Majority Vote Algorithm. This step involves a single pass through the list. Subsequently, it iterates through the list again to verify if the potential candidate indeed appears more than n/2 times. Both iterations are linear with respect to the input size n. Therefore, the overall time complexity is dominated by two linear passes, which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It only requires storing a candidate number and a counter, both of which are independent of the input list's size, N. No additional data structures are created that scale with the input. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty input array	Return None or an appropriate error value/exception, as a majority element cannot exist.
Array with a single element	Return that single element as it is the majority element by definition.
Array with all identical elements	The algorithm should correctly identify this single element as the majority element.
Large input array nearing memory limits	Consider using Boyer-Moore Voting Algorithm for its O(1) space complexity.
Array with a majority element appearing only slightly more than n/2 times	Ensure the algorithm correctly identifies the element that exceeds the n/2 threshold, particularly when it's close.
Integer overflow when counting occurrences (if using a naive approach)	Use a data type that can accommodate larger counts, or the Boyer-Moore algorithm.
Negative numbers in the input array	The solution should work correctly regardless of the sign of the numbers, usually maps will handle this.
No majority element exists	Return None or an appropriate error value/exception to indicate the absence of a majority element after iterating through the array.

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 should I return if no majority element exists?
What is the data type of the numbers in the array, and are negative numbers allowed?
Is the array guaranteed to be non-empty?
By 'majority element', do you mean an element that appears strictly more than n/2 times, where n is the size of the array?
How large can the input array be?

Brute Force Solution

Approach

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

Take the first element from the collection.
Go through the entire collection and count how many times this element appears.
Check if the count is more than half the size of the entire collection. If it is, then we've found our majority element, and we're done.
If the first element is not the majority element, move on to the second element in the collection.
Repeat the counting process for the second element, then the third, and so on, until we find an element that appears more than half the time.
If we reach the end of the collection without finding an element that meets the condition, then there is no majority element.

Code Implementation

def find_majority_element_brute_force(elements):
    collection_size = len(elements)

    for i in range(collection_size):
        current_element = elements[i]
        element_count = 0

        # Count the frequency of the current element
        for j in range(collection_size):
            if elements[j] == current_element:
                element_count += 1

        # Check if current element is the majority
        if element_count > collection_size / 2:
            return current_element

    # No majority element found
    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Pick a candidate number from the list and set its count to 1.
Go through the rest of the list. If the current number is the same as the candidate, increase the count. If it's different, decrease the count.
If the count drops to zero, it means the current candidate is unlikely to be the majority element. Pick the current number in the list as the new candidate and reset the count to 1.
After going through the whole list, you'll have a potential candidate. This candidate is the most likely majority element.
To be sure, count how many times the potential candidate appears in the original list.
If it appears more than half the time, it's the majority element. Otherwise, there is no majority element.

Code Implementation

def find_majority_element(number_list):
    candidate_element = None
    candidate_count = 0

    for number in number_list:
        if candidate_count == 0:
            # If count is 0, assign current number as candidate.
            candidate_element = number
            candidate_count = 1

        elif candidate_element == number:
            candidate_count += 1

        else:
            candidate_count -= 1

    # Verify the candidate is indeed the majority element.
    candidate_frequency = number_list.count(candidate_element)

    if candidate_frequency > len(number_list) // 2:
        return candidate_element
    else:
        # No majority element exists
        return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return None or an appropriate error value/exception, as a majority element cannot exist.
Array with a single element	Return that single element as it is the majority element by definition.
Array with all identical elements	The algorithm should correctly identify this single element as the majority element.
Large input array nearing memory limits	Consider using Boyer-Moore Voting Algorithm for its O(1) space complexity.
Array with a majority element appearing only slightly more than n/2 times	Ensure the algorithm correctly identifies the element that exceeds the n/2 threshold, particularly when it's close.
Integer overflow when counting occurrences (if using a naive approach)	Use a data type that can accommodate larger counts, or the Boyer-Moore algorithm.
Negative numbers in the input array	The solution should work correctly regardless of the sign of the numbers, usually maps will handle this.
No majority element exists	Return None or an appropriate error value/exception to indicate the absence of a majority element after iterating through the array.