Problem Description

You are given an array votes of length n, where each element represents a candidate identifier (which can be a string or an integer). Your task is to implement two distinct voting systems based on this input.

1) Plurality Vote

Determine and return the candidate who received the highest number of votes.

• If multiple candidates are tied for the highest vote count, the tie must be broken by returning the lexicographically smallest candidate if identifiers are strings, or the smallest numeric ID if identifiers are integers.

2) Majority Vote (Boyer–Moore)

Determine and return the candidate who has strictly more than n/2 votes.

• If no such candidate exists, return null (or None).
• This implementation must adhere to specific performance constraints: O(n) time complexity and O(1) extra space complexity (excluding the input array itself). This implies the use of the Boyer–Moore majority vote algorithm.

Input and Output

• Input: votes: List[Candidate]
• Output:
  • pluralityWinner(votes) -> Candidate
  • majorityWinner(votes) -> Candidate | null

Constraints

• The length of the votes array, n, will be between 1 and 10^6 (inclusive).
• Candidate identifiers are guaranteed to be comparable for tie-breaking purposes.

Examples

1. votes = ["A", "B", "A", "C", "B", "A"]
   • Plurality winner: "A" (3 votes)
   • Majority winner: null (3 is not strictly greater than 6/2)
2. votes = [2, 2, 1, 2]
   • Plurality winner: 2
   • Majority winner: 2 (3 is strictly greater than 4/2)