Majority Element

Easy Subject: Arrays & Hashing

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

Problem Statement

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Optimal Solution

Python

Approach: Boyer-Moore Voting Algorithm

We can maintain a candidate and a count. As we iterate through the array, if the current element matches the candidate, we increment the count. If it doesn't, we decrement the count. If the count reaches zero, we switch the candidate to the current element. Because the majority element appears more than half the time, it will always survive the decrements and end up as the final candidate.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate