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

We can solve this problem using several approaches. Here, we'll explore two common and efficient methods:

1. Hash Map (Frequency Counting):

   • Create a HashMap to store the frequency of each element in the array.
   • Iterate through the array, and for each element, increment its count in the HashMap.
   • After iterating, iterate through the HashMap and find the element with a frequency greater than n/2.

2. Boyer-Moore Voting Algorithm:

   • Initialize a candidate element and a counter to 0.
   • Iterate through the array:
     • If the counter is 0, set the current element as the candidate and set the counter to 1.
     • If the current element is equal to the candidate, increment the counter.
     • If the current element is different from the candidate, decrement the counter.
   • The candidate element after the iteration will be the majority element.

Explanation

The Hash Map approach is straightforward and easy to understand. It provides a clear count of each element's occurrences. However, it has a higher space complexity due to the HashMap.

The Boyer-Moore Voting Algorithm is a clever approach with a significantly lower space complexity. It leverages the fact that the majority element appears more than half the time. When we encounter a different element, we decrement the counter. If the counter reaches 0, it means that the current candidate has been "cancelled out" by other elements and we need a new candidate. This algorithm guarantees that the majority element will survive this process.

Code (Java - Boyer-Moore Voting Algorithm)

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    candidate = nums[i];
                    count = 1;
                }
            }
        }
        return candidate;
    }
}

Code (Java - HashMap Approach)

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int majorityElement = -1;
        int maxCount = 0;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() > maxCount) {
                maxCount = entry.getValue();
                majorityElement = entry.getKey();
            }
        }
        return majorityElement;
    }
}

Complexity

Boyer-Moore Voting Algorithm:

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1), as we use only a constant amount of extra space to store the candidate and count.

Hash Map Approach:

• Time Complexity: O(n), we iterate through the array twice (once for counting and once for finding the majority).
• Space Complexity: O(n) in the worst case, when all elements are unique, the HashMap will store all elements.