EasyArrays & Hashing

Majority Element

Find element appearing > n/2 times

Solution Approach

Use Boyer-Moore voting algorithm. Track candidate and count, updating when count reaches 0.

Implementation

def majorityElement(nums):
    # Boyer-Moore voting algorithm
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Complexity

Time:O(n)

Space:O(1)

Asked at

FacebookMicrosoftApple