229. Majority Element II
Problem Description
The given problem requires determining all the elements in an integer array of size n
that appear more than ⌊ n/3 ⌋
times. This threshold implies that we need to find elements which are present in significant quantities, enough to surpass a third of the array's total size. The output should be a list of these dominant elements, and it is implied that the list could include zero, one, or two elements since it's not possible to have more than two elements that each appear more than ⌊ n/3 ⌋
times in the same array.
Intuition
The solution approach stems from a voting algorithm, specifically an extension of the Boyer-Moore Majority Voting algorithm. The original algorithm is designed to find a majority element in an array which appears more than half of the time. In this extended problem, we are looking for elements which appear more than a third of the time, so the array can have at most 2 such elements.
Here is the thinking process broken down:
-
We initiate two potential candidates for the majority element,
m1
andm2
, with placeholders that don't match any elements in the array to start with. These candidates represent the two elements we think might be appearing more than⌊ n/3 ⌋
times. -
Similarly, we have two counters,
n1
andn2
, that help us keep track of the number of times we have encounteredm1
andm2
in the array. -
We iterate through the array (
nums
). For each element (m
), we do the following:- If
m
is equal to one of our current candidates (m1
orm2
), we increment the respective counter (n1
orn2
). - If one of the counters is at zero, it means the respective candidate is not a valid majority element or has been 'voted out', so we replace it with the current element
m
and set its counter to 1. - If
m
is not matching either candidate and both countersn1
andn2
are not zero, we decrement both counters. This is analogous to 'voting out' a candidate, as there must be at least three distinct numbers in the current sequence (thus each couldn't be more than⌊ n/3 ⌋
appearances).
- If
-
Since the counters can be manipulated by elements that are not actually the desired majority elements, we make a final pass through the array to check whether our candidates truly occur more than
⌊ n/3 ⌋
times. We construct the result list by only including candidates that meet this criterion.
This intuition behind the algorithm leverages the idea that if we cancel out triples of distinct elements, any element that appears more than a third of the time will still remain.
Learn more about Sorting patterns.
Solution Approach
The solution code provided implements the approach discussed in the intuition section. Let's walk through the implementation.
-
We initialize two counters
n1
andn2
to zero. These counters will track the number of times we 'see' each candidate. -
Similarly, we start with two candidate variables
m1
andm2
. Values don't matter as long as they're different from each other, hence they're initialized to0
and1
respectively. -
Then, we iterate over all the elements
m
of the input arraynums
and apply the Boyer-Moore Voting algorithm, extended to find elements occurring more than⌊ n/3 ⌋
times:- If
m
is equal to one of our candidates (m1
orm2
), we increase the corresponding counter (n1
orn2
). - If
m
is not equal to either candidate and one of the counters is zero, we set that candidate tom
and reset its counter to 1. This signifies that we are considering a new element as a potential majority candidate. - If
m
is different from both of the existing candidates and both counters are not zero, we decrease both counters. This represents a 'vote out' scenario where we discard a 'set' of three different elements.
- If
-
After the loop, we have two candidates
m1
andm2
. However, these are only potential majority elements because their counters may have been falsely increased by elements that are not actual majorities. -
To ensure that our candidates are valid, we perform a final pass through the array:
- We build a new list by including the candidates that actually occur more than
⌊ n/3 ⌋
times by using the.count()
method.
- We build a new list by including the candidates that actually occur more than
-
The final result consists of this list, which contains zero, one, or two elements occurring more than
⌊ n/3 ⌋
times in the array.
The implementation effectively uses constant space, with only a few integer variables, and linear time complexity, since we make a constant number of passes over the array. The voting algorithm is an elegant solution for such majority element problems, and its extension allows it to be used even with different occurrence thresholds.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider an example array nums = [1, 2, 3, 1, 1, 2, 1]
. This array has a size n = 7
, so we are looking for elements that appear more than ⌊ n/3 ⌋ = ⌊ 7/3 ⌋ = 2
times.
Here's a step-by-step breakdown of how the algorithm would process this example:
-
We initiate two counters
n1
andn2
and set them to zero. These will track occurrences of our candidates. We also start with two variables for the candidatesm1
andm2
, initializing them to0
and1
, respectively. -
We begin iterating over the elements of
nums
:- Iteration 1:
m = 1
. Neitherm1
norm2
is set to1
, and sincen1
is zero, we updatem1
to1
andn1
to1
. - Iteration 2:
m = 2
.m
is not equal tom1
orm2
, andn2
is zero, so we updatem2
to2
andn2
to1
. - Iteration 3:
m = 3
.m
matches neitherm1
norm2
, and both counters are not zero, so we decrease bothn1
andn2
by1
. - Iteration 4:
m = 1
.m
matchesm1
, so we increasen1
to1
(n1
was decreased in the last step). - Iteration 5:
m = 1
.m
matchesm1
, so we increasen1
to2
. - Iteration 6:
m = 2
.m
matchesm2
, so we increasen2
to1
(it was decreased earlier). - Iteration 7:
m = 1
.m
matchesm1
, son1
becomes3
.
- Iteration 1:
-
After the first pass,
n1
andn2
count3
and1
respectively. Our candidates arem1 = 1
andm2 = 2
. -
We need to confirm our candidates' actual occurrences with a second pass:
m1 = 1
appears4
times innums
, which is more than2
(⌊ n/3 ⌋
).m2 = 2
appears2
times, which equals⌊ n/3 ⌋
but does not exceed it.
-
Only
m1
passed the final verification, which means1
appears more than⌊ n/3 ⌋
times in the array. -
The result list contains a single element
[1]
, which is the element occurring more than⌊ n/3 ⌋
times innums
.
Through the approach described in the solution above, we efficiently determined the elements that satisfy the required occurrence condition with this example.
Solution Implementation
1from typing import List
2
3class Solution:
4 def majorityElement(self, nums: List[int]) -> List[int]:
5 # Initialize two potential majority elements and their respective counters.
6 candidate1, candidate2 = None, None
7 count1, count2 = 0, 0
8
9 # Perform Boyer-Moore Majority Vote algorithm
10 for num in nums:
11 # If the current element is equal to one of the potential candidates,
12 # increment their respective counters.
13 if num == candidate1:
14 count1 += 1
15 elif num == candidate2:
16 count2 += 1
17 # If one of the counters becomes zero, replace the candidate with
18 # the current element and reset the counter to one.
19 elif count1 == 0:
20 candidate1, count1 = num, 1
21 elif count2 == 0:
22 candidate2, count2 = num, 1
23 # If the current element is not equal to any candidate and both
24 # counters are non-zero, decrement both counters.
25 else:
26 count1 -= 1
27 count2 -= 1
28
29 # Check whether the candidates are legitimate majority elements.
30 # A majority element must appear more than len(nums) / 3 times.
31 return [m for m in (candidate1, candidate2) if nums.count(m) > len(nums) // 3]
32
1import java.util.List;
2import java.util.ArrayList;
3
4class Solution {
5 public List<Integer> majorityElement(int[] nums) {
6 // Initialize the two potential majority elements and their counters
7 int major1 = 0, major2 = 0;
8 int count1 = 0, count2 = 0;
9
10 // First pass: find the two majority element candidates
11 for (int num : nums) {
12 if (num == major1) {
13 // If the current element is equal to the first candidate, increment its counter
14 count1++;
15 } else if (num == major2) {
16 // If the current element is equal to the second candidate, increment its counter
17 count2++;
18 } else if (count1 == 0) {
19 // If the first candidate's count is zero, select the current element as the first candidate
20 major1 = num;
21 count1 = 1;
22 } else if (count2 == 0) {
23 // If the second candidate's count is zero, select the current element as the second candidate
24 major2 = num;
25 count2 = 1;
26 } else {
27 // If the current element is not equal to either candidate, decrement both counters
28 count1--;
29 count2--;
30 }
31 }
32
33 // Second pass: validate the candidates
34 List<Integer> result = new ArrayList<>();
35 count1 = 0;
36 count2 = 0;
37
38 // Count the actual occurrences of the candidates in the array
39 for (int num : nums) {
40 if (num == major1) {
41 count1++;
42 } else if (num == major2) {
43 count2++;
44 }
45 }
46
47 // Check if the candidates are majority elements (> n/3 occurrences)
48 if (count1 > nums.length / 3) {
49 result.add(major1);
50 }
51 if (count2 > nums.length / 3) {
52 result.add(major2);
53 }
54
55 // Return the list of majority elements
56 return result;
57 }
58}
59
1#include <vector>
2#include <algorithm> // Include algorithm header for count function
3
4class Solution {
5public:
6 std::vector<int> majorityElement(std::vector<int>& nums) {
7 int count1 = 0, count2 = 0; // Initialize counters for two potential majority elements
8 int candidate1 = 0, candidate2 = 1; // Initialize holders for two potential majority elements
9
10 // Use Boyer-Moore Voting Algorithm to find potential majority elements
11 for (int num : nums) {
12 if (num == candidate1) {
13 // If the current element is the same as candidate1, increment count1
14 ++count1;
15 } else if (num == candidate2) {
16 // If the current element is the same as candidate2, increment count2
17 ++count2;
18 } else if (count1 == 0) {
19 // If count1 is 0, replace candidate1 with the current element and reset count1
20 candidate1 = num;
21 count1 = 1;
22 } else if (count2 == 0) {
23 // If count2 is 0, replace candidate2 with the current element and reset count2
24 candidate2 = num;
25 count2 = 1;
26 } else {
27 // If the current element is not equal to either candidate and both counts are non-zero, decrement both counts
28 --count1;
29 --count2;
30 }
31 }
32
33 std::vector<int> result; // Initialize an empty result vector
34 // Check if the candidates are indeed majority elements
35 if (std::count(nums.begin(), nums.end(), candidate1) > nums.size() / 3) {
36 // If candidate1's occurrence is more than a third of the array length, add to the result
37 result.push_back(candidate1);
38 }
39 if (candidate1 != candidate2 && std::count(nums.begin(), nums.end(), candidate2) > nums.size() / 3) {
40 // If candidate2 is different from candidate1 and occurs more than a third of the array length, add to the result
41 // Check candidate1 != candidate2 to avoid counting the same element twice in case of duplicates
42 result.push_back(candidate2);
43 }
44
45 return result; // Return the final result
46 }
47};
48
1function majorityElement(nums: number[]): number[] {
2 // Initialize counters for two potential majority elements
3 let count1: number = 0;
4 let count2: number = 0;
5 // Initialize placeholders for two potential majority elements
6 let candidate1: number = nums[0] || 0;
7 let candidate2: number = nums[1] || 1;
8
9 // Use Boyer-Moore Voting Algorithm to find potential majority elements
10 for (let num of nums) {
11 if (num === candidate1) {
12 // If the current element is the same as candidate1, increment count1
13 count1++;
14 } else if (num === candidate2) {
15 // If the current element is the same as candidate2, increment count2
16 count2++;
17 } else if (count1 === 0) {
18 // If count1 is 0, replace candidate1 with the current element
19 candidate1 = num;
20 count1 = 1;
21 } else if (count2 === 0) {
22 // If count2 is 0, replace candidate2 with the current element
23 candidate2 = num;
24 count2 = 1;
25 } else {
26 // If the current element is not equal to either candidate and both counts are non-zero, decrement both counts
27 count1--;
28 count2--;
29 }
30 }
31
32 // Initialize a result array to store the final majority elements
33 const result: number[] = [];
34
35 // Validate if the candidates are indeed majority elements
36 count1 = nums.filter(num => num === candidate1).length;
37 count2 = nums.filter(num => num === candidate2).length;
38
39 // Add candidate1 to result if count is greater than a third of nums length
40 if (count1 > Math.floor(nums.length / 3)) {
41 result.push(candidate1);
42 }
43
44 // Add candidate2 to result if it's different from candidate1 and count is greater than a third of nums length
45 if (candidate1 !== candidate2 && count2 > Math.floor(nums.length / 3)) {
46 result.push(candidate2);
47 }
48
49 // Return the final result
50 return result;
51}
52
Time and Space Complexity
Time Complexity
The given code implements the Boyer-Moore Voting Algorithm variant to find all elements that appear more than \frac{N}{3}
times in the list. The algorithm is separated into two major phases:
-
Selection Phase: This phase runs through the list once (
O(N)
time), maintaining two potential majority elements along with their corresponding counters. -
Validation Phase: The phase ensures that the potential majority elements actually appear more than
\frac{N}{3}
times. It requires another traversal through the list for each of the two candidates to count the occurrences (O(N)
time per candidate).
The total time complexity is O(N)
for the selection phase plus 2 * O(N)
for the validation phase, resulting in O(N)
.
Space Complexity
The space complexity is O(1)
, as the algorithm uses a constant amount of extra space to maintain the potential majority element candidates and their counters.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.