🧩 Majority Element in an Array (Java)

🚀 Problem Statement

You are given an array arr[]. Your task is to:

• Find the majority element
• A majority element appears more than n/2 times
• If no such element exists, return -1

---

💡 Best Approach: Boyer-Moore Voting Algorithm

This is the most efficient solution because:

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

---

🧠 Intuition

The idea is:

• Keep a candidate and a count
• If count becomes 0 → pick a new candidate
• Increase count if same element appears
• Decrease count if different element appears

👉 At the end, the candidate might be the majority
👉 So we verify it

---

🛠️ Java Implementation

```java id="n4j7zp"
class Solution {
public int majorityElement(int[] arr) {
int count = 0;
int candidate = 0;

    // Step 1: Find candidate
    for (int num : arr) {
        if (count == 0) {
            candidate = num;
        }

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

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

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

}

---

## 🔍 Example



```text id="p9c8x2"
Input:
arr = [2, 2, 1, 2, 3, 2, 2]

Output:
2

---

⏱️ Complexity Analysis

Type	Complexity
Time	O(n)
Space	O(1)

---

⚠️ Important Note

👉 The Boyer-Moore algorithm only guarantees a candidate,
so verification step is necessary.

---

📌 Alternative Approach (HashMap)

```java id="7kq2mv"
import java.util.*;

class Solution {
public int majorityElement(int[] arr) {
HashMap map = new HashMap<>();

    for (int num : arr) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    for (int key : map.keySet()) {
        if (map.get(key) > arr.length / 2) {
            return key;
        }
    }

    return -1;
}

}

---

## 🎯 Final Thoughts

* Use **Boyer-Moore** for optimal performance
* Always **verify the candidate**
* HashMap is easier but uses extra space