Majority Element easy

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

Example 2:

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

Steps to Solve

There are several ways to solve this problem. We'll focus on two efficient approaches:

Approach 1: Using a Hash Map (Dictionary in Python)

1. Initialization: Create a dictionary to store the frequency of each element.
2. Iteration: Iterate through the input array nums. For each element:
   • If the element is already in the dictionary, increment its count.
   • Otherwise, add the element to the dictionary with a count of 1.
3. Finding the Majority Element: Iterate through the dictionary. The element with a count greater than ⌊n / 2⌋ is the majority element.

Approach 2: Boyer-Moore Voting Algorithm

This algorithm is highly efficient in terms of space complexity.

1. Initialization: Initialize a candidate element (candidate) and its count (count) to 0.
2. Iteration: Iterate through the input array nums. For each element:
   • If count is 0, set candidate to the current element and count to 1.
   • If the current element is equal to candidate, increment count.
   • If the current element is different from candidate, decrement count.
3. Return: After iterating through the entire array, candidate will hold the majority element.

Explanation

Approach 1 (Hash Map): This approach is intuitive and easy to understand. It uses extra space to store the frequencies, but it's efficient for handling cases where the majority element's frequency isn't significantly larger than others.

Approach 2 (Boyer-Moore Voting Algorithm): This algorithm is clever. The core idea is that when you encounter a different element, you cancel out a pair of majority element. The remaining element at the end will be the majority element. This approach has a space complexity of O(1). It's particularly efficient when the majority element's frequency is significantly larger than others. It is guaranteed to work because the problem statement states that the majority element always exists.

Code (Python)

Approach 1 (Hash Map):

from collections import Counter

def majorityElement_hashmap(nums):
    counts = Counter(nums)
    n = len(nums)
    for num, count in counts.items():
        if count > n // 2:
            return num

Approach 2 (Boyer-Moore Voting Algorithm):

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

Complexity Analysis

| Approach | Time Complexity | Space Complexity | |--------------------|-----------------|-------------------| | Hash Map | O(n) | O(n) | | Boyer-Moore Voting | O(n) | O(1) |

Where n is the length of the input array nums. The Boyer-Moore Voting Algorithm is preferred for its superior space complexity.