Geeksforgeeks: Majority Element

 Majority Element

Difficulty: Medium

Given an array arr. Find the majority element in the array. If no majority exists, return -1.

A majority element in an array is an element that appears strictly more than arr.size()/2 times in the array.

Examples:

Input: arr[] = [3, 1, 3, 3, 2]
Output: 3
Explanation: Since, 3 is present more than n/2 times, so it is the majority element.

Input: arr[] = [7]
Output: 7
Explanation: Since, 7 is single element and present more than n/2 times, so it is the majority element.

Input: arr[] = [2, 13]
Output: -1
Explanation: Since, no element is present more than n/2 times, so there is no majority element.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ arr.size() ≤ 105
0 ≤ arr[i]≤ 105

Problem Overview:

The task is to find the majority element in an array. A majority element is defined as an element that appears more than n / 2 times in the array, where n is the size of the array. If no such element exists, return -1.

Approach:

To solve this problem efficiently with a time complexity of $O(n)$ and space complexity of $O(1)$, we can utilize the Boyer-Moore Voting Algorithm. This algorithm is well-suited for problems involving majority elements in arrays and works by maintaining a candidate element and a counter.

Key Idea:

• Boyer-Moore Voting Algorithm works by iterating through the array and maintaining two variables:
  1. Candidate: The potential majority element.
  2. Count: A counter to track how many times the candidate appears.
• We iterate through the array:
  • If the current element is the same as the candidate, we increment the count.
  • If the current element is different from the candidate, we decrement the count.
  • If the count reaches zero, we change the candidate to the current element and reset the count to 1.

After the first pass, the candidate might be the majority element. However, we need a second pass to confirm if it is actually the majority element by counting its occurrences and checking if it appears more than n / 2 times.

Algorithm:

1. First pass: Find the potential candidate for the majority element.
2. Second pass: Verify if the candidate occurs more than n / 2 times.

Code Implementation:

public class Solution {
    public int MajorityElement(int[] arr) {
        int n = arr.Length;
        
        // Step 1: Boyer-Moore Voting Algorithm
        int candidate = -1, count = 0;
        
        for (int i = 0; i < n; i++) {
            if (count == 0) {
                candidate = arr[i];
                count = 1;
            } else if (arr[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        // Step 2: Verify if the candidate is the majority element
        int occurrences = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == candidate) {
                occurrences++;
            }
        }
        
        if (occurrences > n / 2) {
            return candidate;
        }
        
        return -1;  // No majority element
    }
}

Explanation:

1. First Pass (Boyer-Moore Voting Algorithm):

   • We iterate through the array and maintain a candidate and a count.
   • If the current element matches the candidate, increment the count.
   • If it doesn't match, decrement the count.
   • When the count becomes zero, we update the candidate to the current element and reset count to 1.

2. Second Pass (Verification):

   • After the first pass, the candidate might be the majority element. To confirm, we count how many times the candidate appears in the array.
   • If it appears more than n / 2 times, return the candidate as the majority element.
   • If it doesn't, return -1 indicating no majority element exists.

Time Complexity:

• Time Complexity: $O(n)$, where n is the size of the array. We perform two passes over the array (one for finding the candidate and one for verifying).
• Space Complexity: $O(1)$, since we are only using a constant amount of extra space.

Example Walkthrough:

Example 1:

• Input: arr[] = [3, 1, 3, 3, 2]
• First Pass:
  • Start with candidate = -1 and count = 0.
  • The first element 3 sets the candidate to 3 and count = 1.
  • The second element 1 decreases the count to 0, and the candidate is updated to 1.
  • The third element 3 sets the candidate to 3 and count = 1.
  • The fourth element 3 increments count to 2.
  • The fifth element 2 decreases count to 1.
  • After the first pass, the candidate is 3.
• Second Pass:
  • Count the occurrences of 3, which appears 3 times.
  • Since 3 appears more than n / 2 times (3 out of 5), return 3.

Output: 3

Example 2:

• Input: arr[] = [2, 13]
• First Pass:
  • The candidate will be either 2 or 13 depending on the iteration, but neither will appear more than once.
• Second Pass:
  • No element appears more than n / 2 times.
• Output: -1

Conclusion:

The Boyer-Moore Voting Algorithm efficiently solves the majority element problem with a time complexity of $O(n)$ and space complexity of $O(1)$. This makes it an optimal solution for large arrays with constraints up to $10^5$.