Majority Element Solution - Leetcode
Understand Majority Element (169 Leetcode) with Solution
This document presents the solution to the problem 169. Majority Element - Leetcode.
This problem requires finding the element, from an unsorted array, appearing more than length(array) / 2 times.
There are multiple ways to find the majority element with different size and space complexity based algorithms.
Here’s one approach in which I’ve sorted the array and then counted the presence of the each element.
func majorityElementUsingSort(nums []int) int {
sort.Ints(nums) // requires importing the sort package.
current := nums[0]
currentCount := 0
majorityElement := nums[0]
majorityElementCount := 0
for _, num := range nums {
if current == num {
currentCount++
} else {
if majorityElementCount < currentCount {
majorityElement = current
majorityElementCount = currentCount
}
current = num
currentCount = 1
}
}
return majorityElement
}
Since the array is sorted, I can choose to just create 4 state variable for counting:
current- The current element in the loopcurrentCount- The count of thecurrentelementmajorityElement- The element having the highest count until nowmajorityElementUsingSort- The count of themajorityElement
How has sorting helped here?
- After we find an element greater than the previous element,
n, we can be sure thatnwill never be found again. - After we’ve seen the last
n, we can compare the count ofnwith the count ofmajorityElementfound so far. - If the count of
nis higher than the count ofmajorityElement,nbecomes themajorityElement.
Time Complexity: O(n * log(n)) due to sorting
Space Complexity: O(n)
AFAIK, there exists atleast 2 solutions that solve this problem in linear time complexity.
- Boyer–Moore majority vote algorithm
- Bit based solution:
- For bit positions from 1 - 31, find the positions that are set in majority of the numbers in the array and then use those positions to construct a number.
- This will be the majority number.
The second approach looked interesting and I choose to implement it.
Approach:
- Create an interger
result, initiailized to0. - For each bit positions from
1 - 31:i- Create an integer counter
currentBitPresenceCount - Find if that position is set on all the
nums:num- Increment
currentBitPresenceCountif the current bit positioniis set onnum
- Increment
- If the value of
currentBitPresenceCountis greater thanlength(nums)- Set the bit position
ionresult
- Set the bit position
- Create an integer counter
I’ve skipped the 32nd bit position because the input is signed integer array. This is not a correct approach as it does not handle the negative numbers. We will look into the correct approach after discussing the shortcomings in the current approach.
func majorityElementUsingBitWiseOperation(nums []int) int {
result := 0
for i := 0; i < 31; i++ {
currentBitPresenceCount := 0
for _, num := range nums {
if num&(1<<i) == (1 << i) {
currentBitPresenceCount++
}
}
if currentBitPresenceCount > len(nums)/2 {
result |= 1 << i
}
currentBitPresenceCount = 0
}
return result
}
Why does it not work with negative numbers?
- Negative numbers are stored using Two’s complement representation.
3becomes00000000000000000000000000000011.-3becomes11111111111111111111111111111101.
In two’s complement representation:
- First, represent 3 in binary:
00000011 - Invert all bits:
11111100 - Add 1:
11111101
This representation breaks the logic.
Here’s the solution that handles the negative numbers too:
func majorityElementUsingBitWiseOperation(nums []int) int {
negativeCount := 0
result := 0
for i := 0; i < 31; i++ {
currentBitPresenceCount := 0
for _, num := range nums {
if num < 0 {
if i == 30 {
negativeCount++
}
num = -num
}
if num&(1<<i) == (1 << i) {
currentBitPresenceCount++
}
}
if currentBitPresenceCount > len(nums)/2 {
result |= 1 << i
}
currentBitPresenceCount = 0
}
if negativeCount > len(nums)/2 {
return -result
}
return result
}
Changes:
- For each number, when the current bit position is 30, it checks if the current number is negative
- If negative, it increments the
negativeCountcounter. - This is done when it is the last bit position so that each number is accounted for only once.
Please do provide some comments if you find the explanation a bit lacking.
