25. Majority Element

Given an array nums of size n, return the majority element. The majority element is the element that appears more than n/2 times. You may assume that the majority element always exists in the array.

Input: nums = [3,2,3]
Output: 3

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Problem Breakdown:

1. We use Boyer-Moore Voting Algorithm. The idea is to maintain a candidate and a count. The majority element will survive the voting process.

• candidate = nums[0]
  count = 0

2. Iterate through the array. If count is 0, set the current element as the new candidate.

• for num in nums:
      if count == 0:
          candidate = num

3. If the current element matches the candidate, increment count. Otherwise, decrement count. The majority element's count can never be fully cancelled out.

•     if num == candidate:
          count += 1
      else:
          count -= 1

4. After the loop, candidate holds the majority element.

• return candidate

Summary:

Boyer-Moore Voting: maintain a candidate and count. When count reaches 0, pick a new candidate. The majority element (appearing more than n/2 times) will always be the final candidate since it cannot be fully outvoted.

Time and Space Complexity:

Time Complexity: O(n) - single pass through the array.

Space Complexity: O(1) - only two variables used.

Python Solution:

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
        if num == candidate:
            count += 1
        else:
            count -= 1
    return candidate

JavaScript Solution:

var majorityElement = function(nums) {
    let candidate = nums[0], count = 0;
    for (const num of nums) {
        if (count === 0) candidate = num;
        count += (num === candidate) ? 1 : -1;
    }
    return candidate;
};

Java Solution:

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