Problem Statement

Given an array nums of size n, find the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times.

You can 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

Constraints:

• n ≥ 1
• Majority element always exists

---

Approach to Solve the Problem (Simple Language)

There are multiple ways to solve this problem. We will discuss two common approaches.

---

Approach 1: Using HashMap (Counting Frequency)

1. Count how many times each element occurs using a HashMap.
2. Iterate through the map to find the element whose frequency is greater than n / 2.
3. Return that element.

Steps in short:

• Create a HashMap to store counts of elements.
• Loop through nums, updating counts.
• Loop through map entries to find majority element.

---

Approach 2: Boyer-Moore Voting Algorithm (Optimal)

1. Initialize candidate and count.
2. Iterate through the array:
   • If count is 0, set candidate = current element.
   • If current element == candidate, increment count.
   • Else, decrement count.
3. The candidate at the end is the majority element.

Why it works:

• The majority element appears more than n / 2 times, so it will remain the candidate at the end.

Optimal Approach is O(n) time and O(1) space.

---

Java Code Solution – Boyer-Moore

public class MajorityElement {

    public static int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }

            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,1,1,1,2,2};
        int result = majorityElement(nums);
        System.out.println("Majority element is: " + result); // Output: 2
    }
}

---

Dry Run Example – Boyer-Moore

Input:

nums = [2,2,1,1,1,2,2]

Step-by-step Execution:

Step	num	candidate	count	Explanation
1	2	2	1	count was 0, set candidate to 2
2	2	2	2	num == candidate → increment count
3	1	2	1	num != candidate → decrement count
4	1	2	0	num != candidate → decrement count
5	1	1	1	count = 0 → set candidate = 1
6	2	1	0	num != candidate → decrement count
7	2	2	1	count = 0 → set candidate = 2

Result: candidate = 2 → majority element.

---

Textual Diagram for Understanding

Array: [2,2,1,1,1,2,2]
Candidate & Count Updates:

Start: candidate=0, count=0

num=2 -> count=0 -> candidate=2, count=1
num=2 -> num==candidate -> count=2
num=1 -> num!=candidate -> count=1
num=1 -> num!=candidate -> count=0
num=1 -> count=0 -> candidate=1, count=1
num=2 -> num!=candidate -> count=0
num=2 -> count=0 -> candidate=2, count=1

Majority element = 2

---

Complexity Analysis

• Time Complexity: O(n)
  • One pass through the array.
• Space Complexity: O(1)
  • Only variables candidate and count used.

---

The Boyer-Moore algorithm is optimal and elegant for this problem.