Majority Element II: Boyer-Moore Voting Algorithm

Problem Explanation:

In this problem, you're given an array of integers where each number represents a vote for a candidate. The goal is to find all the candidates that have received more than one-third of the total votes. If no such candidate exists, return an empty list. The result should be returned in ascending order.Example 1:

• Input: arr[] = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6]
• Output: [5, 6]
• Explanation: Both 5 and 6 appear more than 113311 times (i.e., more than about 3.67 times).

Example 2:

• Input: arr[] = [1, 2, 3, 4, 5]
• Output: []
• Explanation: No element appears more than 5335 times (i.e., more than about 1.67 times).

Solution Approach:

To solve this problem efficiently, we can use theBoyer-Moore Voting Algorithm, which is designed to find majority elements in linear time with constant space. The algorithm works in two phases:

1. Candidate Selection (First Pass):Traverse through the array and maintain two potential candidates (elm1 and elm2) along with their counts (count1 and count2).If the current number matches one of the candidates, increment its count.If one of the counts is zero (i.e., no candidate assigned), assign the current number as a new candidate.If the current number doesn't match any candidate and both counts are non-zero, decrement both counts.
2. Validation (Second Pass):After identifying two potential candidates from the first pass, we need to verify if they actually appear more than n33n times.Reset the counts and traverse through the array again to count how many times each candidate appears.
3. Return Result:If a candidate's count exceeds n33n, it is added to the result list.Finally, sort the result list in ascending order before returning it.

Edge Cases:

• If the array has fewer than three elements, any element that appears more than once should be considered a majority element.
• If no element appears more than n33n times, return an empty list.

Code Implementation:

class Solution:
    def findMajority(self, arr):
        if not arr:
            return []
        
        # Initialize variables for two potential majority elements
        elm1, elm2 = None, None
        count1, count2 = 0, 0
        
        # First pass: Find potential candidates for majority elements
        for num in arr:
            if num == elm1:
                count1 += 1
            elif num == elm2:
                count2 += 1
            elif count1 == 0:
                elm1 = num
                count1 = 1
            elif count2 == 0:
                elm2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1
        
        # Second pass: Verify if they are actually majority elements
        count1, count2 = 0, 0
        for num in arr:
            if num == elm1:
                count1 += 1
            elif num == elm2:
                count2 += 1
        
        # Check if they appear more than n/3 times and return result in sorted order
        result = []
        if count1 > len(arr) / 3:
            result.append(elm1)
        if count2 > len(arr) / 3:
            result.append(elm2)
        
        result.sort() # Ensure ascending order as required by problem statement
        return result

# Example usage:
# arr = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6]
# sol = Solution()
# print(sol.findMajority(arr)) # Output: [5, 6]        

Time and Space Complexity:

• Time Complexity:The algorithm makes two passes over the array. Each pass takes O(n)O(n) time where nn is the size of the array. Therefore, the overall time complexity is O(n)O(n).
• Space Complexity:The space complexity is O(1)O(1) because we are only using a few extra variables (for candidates and counts), regardless of the size of the input array.

Conclusion:

The Boyer-Moore Voting Algorithm provides an efficient solution to finding elements that appear more than n/3 times in an array. With linear time complexity and constant space usage, this approach is optimal for large datasets where brute-force methods would be too slow or memory-intensive.