Solution Explanation: Majority Element

The problem asks to find the majority element in an array, which is the element that appears more than ⌊n/2⌋ times (where n is the array's length). We're guaranteed that such an element exists.

Several approaches exist, but the most efficient is the Boyer-Moore Voting Algorithm. This algorithm cleverly leverages the fact that the majority element's count outweighs all other elements combined.

Boyer-Moore Voting Algorithm

This algorithm works in two phases:

Phase 1: Candidate Selection

1. Initialization: We start with a candidate element (initially null or any element from the array) and a count (initialized to 0).
2. Iteration: We iterate through the array. For each element:
   • If the count is 0, we set the candidate to the current element and set count to 1.
   • If the current element is equal to the candidate, we increment count.
   • If the current element is different from the candidate, we decrement count.
3. Result: After iterating through the entire array, the candidate will hold a potential majority element. This is not guaranteed to be the actual majority element yet, as it just represents an element that is at least as frequent as any other element individually.

Phase 2: Verification (Not needed in this problem)

Strictly speaking, a second phase is needed to verify if the candidate is indeed the majority element. This involves counting the occurrences of the candidate in the array. Since the problem statement ensures the majority element's existence, we can skip this phase.

Why it works: The algorithm cleverly cancels out non-majority elements. If we encounter a non-majority element, the count decreases. Eventually, the count will reach 0, and a different candidate will take over. The majority element, because of its larger frequency, will always have its count reset to 0 slower than others.

Time and Space Complexity:

• Time Complexity: O(n) - We iterate through the array once.
• Space Complexity: O(1) - We use only constant extra space to store candidate and count.

Code Examples

The following code examples demonstrate the Boyer-Moore algorithm in various programming languages:

Python:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
                count = 1
            elif num == candidate:
                count += 1
            else:
                count -= 1
        return candidate
 

Java:

class Solution {
    public int majorityElement(int[] nums) {
        Integer candidate = null;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

C++:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
};

(Other languages like JavaScript, Go, TypeScript, etc., would follow a similar structure.)

These codes all implement the same core logic: iterating through the array and updating the candidate and count based on the comparison with the current element. The concise nature of the algorithm contributes to its efficiency.