12.02.2024
169. Majority Element easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/503
Problem TLDR
Element with frequency > nums.len / 2.
Intuition
First thing is to understand the problem, as we need to find not only the most frequent element, but frequency is given > nums.len / 2 by the input constraints.
Next, let’s observe examples:
There are properties derived from the observation:
sequence can spread other elements between the common
common can exist in several islands
the second common island size is less than first common
island can be single one
We can write an ugly algorithm full of ‘ifs’ now.
fun majorityElement(nums: IntArray): Int {
var a = -1
var b = -1
var countA = 1
var countB = 0
var currCount = 1
var prev = -1
for (x in nums) {
if (x == prev) {
currCount++
if (currCount > nums.size / 2) return x
} else {
if (currCount > 1) {
if (a == -1) a = prev
else if (b == -1) b = prev
if (prev == a) {
countA += currCount
}
if (prev == b) {
countB += currCount
}
}
currCount = 1
}
prev = x
}
if (a == -1) a = prev
else if (b == -1) b = prev
if (prev == a) {
countA += currCount
} else if (prev == b) {
countB += currCount
}
return if (a == -1 && b == -1) {
nums[0]
} else if (countA > countB) a else b
}
Approach
However, for our pleasure, there is a comment section of leetcode exists, find some big head solution there: it works like a magic for me still. Count the current frequency and decrease it by all others. If others are sum up to a bigger value, our candidate is not the hero.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun majorityElement(nums: IntArray): Int {
var a = -1
var c = 0
for (x in nums) {
if (c == 0) a = x
c += if (x == a) 1 else -1
}
return a
}
pub fn majority_element(nums: Vec<i32>) -> i32 {
let (mut a, mut c) = (-1, 0);
for x in nums {
if c == 0 { a = x }
c += if x == a { 1 } else { -1 }
}
a
}