Domain 1EasyCORE

Majority Element

The problem requires finding the majority element in an array `nums` where the majority element appears more than `⌊n / 2⌋` times. The input is an array of integers, and the output should be the integer that meets the criteria of being the majority element. We are guaranteed that a majority element always exists in the array.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Divide and Conquer#Bit Manipulation

169. Majority Element

Model: qwen2.5-coder:14b
Topics: Array,Divide and Conquer,Bit Manipulation
FAANG asked: 1
Acceptance rate: 60.2%


Problem Breakdown

The problem requires finding the majority element in an array nums where the majority element appears more than ⌊n / 2⌋ times. The input is an array of integers, and the output should be the integer that meets the criteria of being the majority element. We are guaranteed that a majority element always exists in the array.

Intuition

A brute-force approach would involve counting the occurrences of each element using a hash map or dictionary, then iterating through the counts to find the element with more than ⌊n / 2⌋ occurrences. However, this approach has a time complexity of O(n) and space complexity of O(n), which is not optimal.

The key insight for a better approach is the Boyer-Moore Voting Algorithm. This algorithm works by maintaining a candidate for the majority element and a count. As we iterate through the array, if the count is zero, we set the current element as the candidate and increment the count. If the current element is the same as the candidate, we increment the count; otherwise, we decrement the count. By the end of the iteration, the candidate will be the majority element.

Approach

We use the Boyer-Moore Voting Algorithm to find the majority element. The algorithm involves two steps:

  1. Finding a Candidate: Iterate through the array and maintain a candidate for the majority element and a count. If the count is zero, set the current element as the candidate and increment the count. If the current element is the same as the candidate, increment the count; otherwise, decrement the count.
  2. Verifying the Candidate: Although the problem guarantees that a majority element always exists, we can optionally verify the candidate by counting its occurrences in the array.

The algorithm has a linear time complexity and constant space complexity, making it efficient for large arrays.

Complexity Analysis

  • Time Complexity: O(n) - We iterate through the array once to find the candidate and optionally once more to verify.
  • Space Complexity: O(1) - We use only a constant amount of extra space for the candidate and count variables.

Solution

def majorityElement(nums):
    # Step 1: Find a candidate for the majority element
    candidate = None
    count = 0
    
    for num in nums:
        if count == 0:
            candidate = num
            count += 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    
    # Step 2: Verify the candidate (optional, as problem guarantees majority element)
    # count = nums.count(candidate)
    
    return candidate

# Example usage:
print(majorityElement([3, 2, 3]))  # Output: 3
print(majorityElement([2, 2, 1, 1, 1, 2, 2]))  # Output: 2

Edge Cases Handled

  • Single Element Array: The algorithm works correctly as the single element is trivially the majority.
  • All Elements Same: The candidate will be the same element throughout, and it will be the majority.
  • Alternating Elements: If elements alternate but one appears more than half the time, the algorithm will correctly identify it as the majority.

The solution provided is correct, efficient, and clear. It adheres to the constraints and handles all edge cases appropriately. The Boyer-Moore Voting Algorithm ensures linear time complexity and constant space complexity, making it optimal for this problem.