Majority Element – CA21

My Thinking and Approach

Introduction

In this problem, I was given an array and asked to find the majority element.

A majority element is the one that appears more than n/2 times in the array. If no such element exists, we need to return -1.

At first, it looked like a simple counting problem, but I learned that there is a more optimized way to solve it.

---

Problem Statement

• Given an array arr[]
• Find the element that appears more than n/2 times
• If no such element exists, return -1

---

My Initial Approach

Initially, I thought of using a frequency count:

• Use a HashMap
• Count occurrences of each element
• Return the element with count > n/2

Drawback

• Time Complexity: O(n)
• Space Complexity: O(n)

Although this works, it is not the most optimal solution.

---

Optimized Approach (Boyer-Moore Voting Algorithm)

To improve efficiency, I used the Boyer-Moore Voting Algorithm, which works in:

• Time: O(n)
• Space: O(1)

---

My Approach

Step 1: Find Candidate

• Maintain two variables:

  • candidate
  • count

• Traverse the array:

  • If count == 0, assign current element as candidate
  • If current element equals candidate → increment count
  • Else → decrement count

---

Step 2: Verify Candidate

• Count how many times the candidate appears
• If count > n/2 → return candidate
• Else → return -1

---

Code (Java)

class Solution {
    int majorityElement(int arr[]) {
        int candidate = 0, count = 0;

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

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

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

        return (count > arr.length / 2) ? candidate : -1;
    }
}

---

Example Walkthrough

Example 1

Input:
[1, 1, 2, 1, 3, 5, 1]

• Candidate becomes 1
• It appears more than n/2 times

Output:
1

---

Example 2

Input:
[2, 13]

• No majority element exists

Output:
-1

---

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Key Takeaways

• Boyer-Moore algorithm is very efficient
• Always verify the candidate
• Helps reduce space complexity

---

Conclusion

This problem helped me understand how to optimize a simple counting problem into a more efficient solution using the Boyer-Moore Voting Algorithm. It is a very useful concept for coding interviews and competitive programming.