Leetcode 169. Majority Element
Problem Explanation
We are given an array of size n and we need to find the majority element. The majority element is the element that appears more than โ n/2 โ times in the array. We can assume that the array is never empty and the majority element always exists in the array.
The problem can be solved by using the Boyer-Moore Voting Algorithm. The basic idea of the Boyer-Moore Voting Algorithm is that in each round of voting, we maintain a candidate, that could potentially be the majority element. We vote (add count) for each occurrence of this candidate and vote against (subtract count) for every other element.
Through rounds of voting, the majority would gain more votes and the minority would lose votes until the majorityโs votes win out. This happens because the majority element appears more than โ n/2 โ times, thus it is guaranteed to result in positive votes at the end.
Solution Approach
-
Initialize a variable
count
to 0 and a variablecandidate
to some value. -
For each number
num
in our given array, ifcount
is 0, setnum
as thecandidate
. -
If
num
equalscandidate
, incrementcount
by 1. Ifnum
doesn't equalcandidate
, decrementcount
by 1. -
Once all numbers have been assessed,
candidate
will be the majority element.
Solution Walkthrough
-
Take an example
{3,2,3}
. We initializecount
as 0 andcandidate
as None. -
For the first element 3,
count
is 0, so we make 3 ascandidate
and incrementcount
to 1. -
The next number is 2, which is not equal to
candidate
, so we decrementcount
to 0. -
The last number is 3,
count
is 0, so we make 3 ascandidate
and incrementcount
to 1. -
Now, all numbers have been assessed and our
candidate
is 3 which is indeed the majority element.
Python Solution
1 2python 3class Solution: 4 def majorityElement(self, nums: List[int]) -> int: 5 count = 0 6 candidate = None 7 8 for num in nums: 9 if count == 0: 10 candidate = num 11 count += (1 if num == candidate else -1) 12 13 return candidate
Java Solution
1 2java 3public class Solution{ 4 public int majorityElement(int[] nums) { 5 int count = 0; 6 Integer candidate = null; 7 8 for (int num: nums){ 9 if (count == 0){ 10 candidate = num; 11 } 12 count += (num == candidate) ? 1: -1; 13 } 14 15 return candidate; 16 } 17}
JavaScript Solution
1 2javascript 3class Solution { 4 majorityElement(nums) { 5 let count = 0; 6 let candidate = null; 7 8 for (let num of nums) { 9 if (count == 0) { 10 candidate = num; 11 } 12 count += (num == candidate) ? 1 : -1; 13 } 14 15 return candidate; 16 } 17}
C++ Solution
1 2c++ 3class Solution { 4public: 5 int majorityElement(vector<int>& nums) { 6 int count = 0; 7 int candidate; 8 9 for (int num: nums) { 10 if (count == 0){ 11 candidate = num; 12 } 13 if (num == candidate){ 14 count++; 15 } 16 else { 17 count--; 18 } 19 } 20 21 return candidate; 22 } 23};
C# Solution
1 2csharp 3public class Solution { 4 public int MajorityElement(int[] nums) { 5 int count = 0; 6 int? candidate = null; 7 8 foreach (int num in nums) { 9 if (count == 0){ 10 candidate = num; 11 } 12 count += (num == candidate) ? 1 : -1; 13 } 14 15 return candidate.Value; 16 } 17}
Note
In the given solutions, we use the ternary operator to increment or decrement the count based on whether the current number is the candidate or not. If the current number is the candidate, we increment the count, else we decrement the count.The final majority element is the one that remains after all pairs of non-equal elements are removed. The count of candidate if it's a majority element will always be positive at the end. Therefore, by maintaining a count that increments when we encounter the candidate and decrements when we encounter other elements, we ensure that the majority's votes win.
Time Complexity
This algorithm works in O(n) time where n is the total number of elements in the array. This is because we are iterating over the array just once. For each element, we are performing a constant amount of work (updating the count and possibly setting the candidate). Therefore, the overall time complexity is O(n).
Space Complexity
The space complexity of the algorithm is O(1), that is, constant space complexity. We have used only a constant amount of space to store the candidate and the count. Regardless of the size of the input, the amount of space used does not increase.
Conclusion
The problem of finding the majority element in an array can be solved efficiently using the Boyer-Moore Voting Algorithm. Our solutions in Python, JavaScript, and Java implement this algorithm and successfully find the majority element with O(n) time complexity and O(1) space complexity, making it a practical solution for large inputs.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.