5.10.2023
229. Majority Element II medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/360
Problem TLDR
Elements with frequency > size / 3
Intuition
The naive solution, which is to count frequencies, can be this one-liner:
fun majorityElement(nums: IntArray) = nums
.groupBy { it }
.filter { (k, v) -> v.size > nums.size / 3 }
.map { (k, v) -> k }
However, to solve it in O(1) we need to read the hint
: Moore algo.
One idea is that there are at most only two
such elements can coexist:
// 111 123 333
// 1111 1234 4444
// 11111 12345 55555
The second idea is a clever counting of three
buckets: first
candidate, second
candidate and others. We decrease candidates counters if x
in the others
bucket, and change candidate if it’s counter 0
.
Approach
Steal someone’s else solution or ask ChatGPT about Moore
algorithm to find majority element.
make sure you understand why the resulting elements are majority
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun majorityElement(nums: IntArray): List<Int> {
var x1 = Int.MIN_VALUE
var x2 = Int.MIN_VALUE
var count1 = 0
var count2 = 0
for (x in nums) when {
x != x2 && count1 == 0 -> x1 = x.also { count1 = 1 }
x != x1 && count2 == 0 -> x2 = x.also { count2 = 1 }
x == x1 -> count1++
x == x2 -> count2++
else -> {
count1 = maxOf(0, count1 - 1)
count2 = maxOf(0, count2 - 1)
}
}
return buildList {
if (nums.count { it == x1 } > nums.size / 3) add(x1)
if (nums.count { it == x2 } > nums.size / 3) add(x2)
}
}