Given an integer array of size n
, find all elements that appear more than ⌊ n/3 ⌋
times.
For example:
nums = [3,2,3]
should return [3]
nums = [1]
should return [1]
nums = [1,2]
should return [1, 2]
Could you solve the problem in linear time and in O(1)
space?
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:
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:
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
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:
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
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. |