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 one that appears more than n/2 times in the array.

---

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 Thought

At first, I considered:

• Using a hashmap to count frequencies
• Returning the element with highest count

But this approach uses extra space.

---

Key Observation

There can be at most one majority element.

This allows a more optimized approach without extra space.

---

Optimized Approach

I decided to use Moore’s Voting Algorithm.

Logic:

• Maintain a candidate and count
• Increase count if same element appears
• Decrease count if different element appears
• Final candidate may be majority

---

My Approach (Step-by-Step)

1. Initialize:

• candidate = None
• count = 0

1. Traverse array:

• If count == 0: → set candidate = current element
• If element == candidate: → count += 1
• Else: → count -= 1

1. Verify candidate:

• Count occurrences of candidate
• If count > n/2 → return candidate
• Else → return -1

---

Code (Python)

Below is the implementation clearly separated inside a code block:

```python id="y3sk9q"
class Solution:
def majorityElement(self, arr):
candidate = None
count = 0

    for num in arr:
        if count == 0:
            candidate = num
        if num == candidate:
            count += 1
        else:
            count -= 1

    count = 0
    for num in arr:
        if num == candidate:
            count += 1

    if count > len(arr) // 2:
        return candidate
    return -1

---

## Example Walkthrough

### Input:



```text id="l4u2qg"
arr = [1, 1, 2, 1, 3, 5, 1]

Steps:

• Candidate becomes 1
• Count stabilizes with majority
• Verify count > n/2

Output:

```text id="qv6y2x"
1

---

## Complexity Analysis

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

---

## Key Takeaways

* Only one majority element can exist
* Moore’s Voting Algorithm is optimal
* Verification step is important

---

## Conclusion

This problem helped me understand how to find the majority element efficiently using a constant space approach.

---