The algorithm relies on a cancellation idea:

• Imagine pairing up different elements in the array.
• Every time you encounter two different elements, they cancel each other out.
• Since the majority element appears more than half the time, it will always survive cancellation and remain at the end.

Majority vs the Most common

• The most common element Is Not the majority element:
  • The array [0,1,**2,2**,3] or [0,1,**2,2**] doesn’t have the majority element, the most common element 2 will be cancel out by the end of the Boyer-Moore Voting process.
• The majority element is the most common element.
  • The array [0,1,**2,2,2**] has the majority element and it is the majority element.

⭐️ (Easy) 169. Majority Element, NeetCode 250

https://leetcode.com/problems/majority-element/description/

Last review: Sep 14, 2025 Next review: I couldn’t recall the essential concept.

Hash Map

• Time Complexity O(n)
• Space Complexity O(n)

func majorityElement(nums []int) int {
	n := len(nums)

	count := make(map[int]int)

	for _, num := range nums {
		count[num]++
		if count[num] > n/2 {
			return num
		}
	}
	return -1
}

Sorting + Sliding Window

• Time Complexity O(n log n)
• Space Complexity O(log n)

func majorityElement(nums []int) int {
	n := len(nums)

	sort.Ints(nums)

	L := 0
	for R := 0; R < n; R++ {
		if nums[R] != nums[L] {
			L = R
		}
		if R-L+1 > n/2 {
			return nums[R]
		}
	}
	return -1
}

Boyer-Moore Voting ⭐️

• Time Complexity O(n)