We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Majority Element

Number: 169

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Amazon, Meta, Bloomberg, tcs, Autodesk, Apple, Accenture, DE Shaw, Oracle, Deloitte, Adobe, Uber, Nvidia, Yandex, eBay, Media.net, Salesforce, Pwc, Zenefits

Problem Description

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.

Key Insights

  • The majority element appears more than half the length of the array.
  • A simple hash table approach can count occurrences, but a more efficient solution exists.
  • The Boyer-Moore Voting Algorithm finds the majority in O(n) time and O(1) space.
  • The algorithm maintains a candidate and a counter, adjusting the candidate when the count drops to zero.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(1)

Solution

We use the Boyer-Moore Voting Algorithm to identify the majority element. The algorithm iterates through the array using two variables: one for the candidate and one for the count. Initially, we set the candidate to an arbitrary value and count to 0. For each element, if the count is 0, we update the candidate to the current element. Then, if the current element is the same as the candidate, we increment the count; otherwise, we decrement it. Since the majority element appears more than n/2 times, it will remain as the candidate by the end of the iteration.

Code Solutions

# Python implementation of the Boyer-Moore Voting Algorithm

def majorityElement(nums):
    # Initialize candidate and counter
    candidate = None
    count = 0
    
    # Iterate over each number in the input list
    for num in nums:
        # If count is 0, choose the current number as the candidate
        if count == 0:
            candidate = num
        # Increment count if the current number equals the candidate, otherwise decrement
        count += 1 if num == candidate else -1
    # Return the candidate, which is the majority element
    return candidate

# Example usage
print(majorityElement([2,2,1,1,1,2,2]))  # Output: 2
← Back to All Questions