ASSIGNMENT 21

1.Majority Element

Problem

Given an array, find the majority element.
A majority element is an element that appears more than n/2 times in the array. 

If no such element exists, return -1

Example

Input:
1, 1, 2, 1, 3, 5, 1

Output:
1

Because it appears more than half of the array size 

Approach Used

Moore’s Voting Algorithm (Optimal Approach)

This is the most efficient approach:
•Time Complexity → O(n)
•Space Complexity → O(1)

Idea:
We cancel out different elements and keep track of a potential majority element.
If a majority element exists, it will remain at the end. 

Step-by-Step Explanation

Step 1: Initialize Variables
•Start with a candidate element
•Maintain a count variable

Step 2: Traverse the Array

Go through each element in the array one by one.

Step 3: Update Candidate
•If count becomes 0 → choose the current element as the new candidate
•Set count to 1

Step 4: Compare Elements
•If the current element is equal to the candidate → increase count
•If different → decrease count

This represents cancelling out different elements

Step 5: Find Potential Majority

After one full traversal:
•The remaining candidate is a possible majority element

But it is not guaranteed yet

Step 6: Verify the Candidate

Count how many times the candidate appears:
•If it appears more than n/2 → it is the majority element
•Otherwise → return -1

Verification is necessary because a majority may not exist

`class Solution:
def majorityElement(self, arr):
# Step 1: Find candidate
count = 0
candidate = None

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

    # Step 2: Verify candidate
    if arr.count(candidate) > len(arr) // 2:
        return candidate

    return -1`

Complexity Analysis

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

Conclusion

The Majority Element problem is a classic example of how smart observation can reduce complexity. Instead of counting every element, Moore’s Voting Algorithm cleverly cancels out non-majority elements.