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

There are several approaches to solve this problem. We'll detail two common and efficient solutions:

1. Using a Dictionary (Hash Map):

• Count Occurrences: Iterate through the array, using a dictionary to store each number as a key and its count as a value.
• Find Majority: After counting, iterate through the dictionary and find the key (number) with a count greater than n/2.

2. Boyer-Moore Voting Algorithm:

• Initialize: Start with a candidate element (candidate) and its count (count), both initialized to 0.
• Iterate: Iterate through the array.
  • 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.
• Return: After the iteration, candidate will hold the majority element.

Explanation

1. Dictionary Approach: This approach is straightforward and easy to understand. It uses extra space to store the counts, making it less space-efficient than the Boyer-Moore algorithm but conceptually simpler.

2. Boyer-Moore Voting Algorithm: This algorithm is remarkably efficient. The core idea is that when a different element is encountered, it cancels out a vote for the current candidate. If the majority element truly exists, its votes will always outnumber the votes of other elements combined. This ensures that the final candidate is the majority element. It achieves linear time complexity with constant space complexity, making it superior in terms of efficiency for large arrays.

Code (C#)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    // Dictionary Approach
    public int MajorityElementDictionary(int[] nums) {
        Dictionary<int, int> counts = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (counts.ContainsKey(num)) {
                counts[num]++;
            } else {
                counts[num] = 1;
            }
        }
        int n = nums.Length;
        foreach (KeyValuePair<int, int> kvp in counts) {
            if (kvp.Value > n / 2) {
                return kvp.Key;
            }
        }
        return -1; // Should not reach here as the problem states majority element always exists
    }

    // Boyer-Moore Voting Algorithm
    public int MajorityElementBoyerMoore(int[] nums) {
        int candidate = 0;
        int count = 0;
        foreach (int num in nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

Complexity

Dictionary Approach:

• Time Complexity: O(n) - due to two iterations through the array and dictionary.
• Space Complexity: O(n) - in the worst case, the dictionary could store all unique elements.

Boyer-Moore Voting Algorithm:

• Time Complexity: O(n) - single pass through the array.
• Space Complexity: O(1) - constant extra space is used. This is the preferred approach due to its better space efficiency.