Majority Element | Leetcode 169 | Explained in Python

The “Majority Element” problem (LeetCode #169) asks you to find the value that appears strictly more than ⌊ n / 2 ⌋ times in an integer array nums of length n. The input is guaranteed to contain such an element, so exactly one answer exists.

Example
Input [2, 2, 1, 1, 1, 2, 2]
Output 2 (because 2 occurs 4 > 7/2 = 3 times)

Why it matters: detecting a clear majority is a classic voting-style task, leading to the elegant Boyer-Moore Voting Algorithm used in stream processing and data analytics.

Here’s the [Problem Link] to begin with.

Brute Force Solution (Double Loop)

Intuition & Approach

• Compare every element against every other element, counting matches.
• The element whose count exceeds n // 2 is the majority.

Although straightforward, this is quadratic time and thus unsuitable for large arrays.

Code Implementation

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            cnt = 0
            for j in range(n):
                if nums[j] == nums[i]:
                    cnt += 1          # increase count for each match
            if cnt > (n // 2):        # majority found
                return nums[i]

Code Explanation

• Outer loop picks a potential candidate nums[i].
• Inner loop counts its total occurrences.
• The first value whose count passes ⌊n/2⌋ is returned immediately.

Dry Run (Input [3, 3, 4])

1. i = 0 (nums[i] = 3) → inner count = 2 → 2 > 1 ? Yes → return 3.

Time & Space Complexity

• Time: O(n²) – nested scan across all pairs.
• Space: O(1) – constant extra memory.

Conclusion

Easy to code, but far too slow for anything beyond a few thousand elements.

Better Solution (Hash Map Frequency)

Intuition & Approach

• Maintain a hash map num → frequency.
• One linear pass builds the map; a second (or running check) locates the key whose frequency exceeds n // 2.

Code Implementation

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        hash_map = dict()              # stores frequency of each number
        n = len(nums)

        # Build frequency table
        for num in nums:
            hash_map[num] = hash_map.get(num, 0) + 1

        # Find the element with frequency > n//2
        for k, v in hash_map.items():
            if v > n // 2:
                return k

Code Explanation

• Counting Pass: Updates the dictionary in O(1) average time per insertion.
• Scanning Pass: Reads each (key, value) until it finds the majority.

Dry Run (Input [2, 2, 1])

• Hash map after pass 1: {2: 2, 1: 1}
• Pass 2 returns 2 because 2 > 3//2.

Time & Space Complexity

• Time: O(n) – linear over the array.
• Space: O(k) where k ≤ n is the number of distinct elements.

Conclusion

Fast and clear, but extra hash-map storage may be unnecessary when we know a majority exists.

Optimal Solution (Boyer-Moore Voting Algorithm)

Intuition & Approach

1. Idea: Pair off different elements so they “cancel” one another.
2. Candidate & Count:
   • When count == 0, adopt the current number as the new candidate.
   • Increment count if the next number equals candidate, otherwise decrement.
3. Because the majority element appears more than all others combined, it survives these cancellations.

Code Implementation

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = nums[0]   # potential majority element
        count = 0             # vote balance

        for i in range(0, len(nums)):
            if count == 0:            # no current leader
                candidate = nums[i]
                count = 1             # start fresh vote
            elif nums[i] == candidate:
                count += 1            # same as leader → gain vote
            else:
                count -= 1            # different → lose vote

        return candidate              # guaranteed to be majority

Code Explanation

• Vote Tally: Each matching number contributes +1; each different number contributes −1.
• Reset Rule: When the balance hits 0, pick a new candidate (the old one is canceled out by equal opposition).
• Because the true majority owns more than half the votes, it cannot be fully canceled and emerges at the end.

Dry Run (Input [2, 2, 1, 1, 1, 2, 2])

Loop ends with candidate = 2, which is indeed the majority.

Time & Space Complexity

• Time: O(n) – single pass.
• Space: O(1) – just two variables.

Conclusion

The Boyer-Moore algorithm is the perfect fit:

• One pass
• Constant space
• Mathematically guaranteed if a majority exists

It’s the go-to answer for interviewers whenever you’re asked to find a majority element in linear time.

Final Thoughts

Understanding how pairwise cancellation reduces memory from a hash map to two variables is a valuable lesson you can reuse in many stream-processing and majority-vote problems. Happy coding!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.