Majority Element - LeetCode Solution in C++, Java, Python

1. Introduction

The "Majority Element" problem focuses on finding an element in an array that appears more than half the time (i.e., more than ⌊n / 2⌋ times). It's a common problem to test understanding of array manipulation and voting algorithms.

2. Problem

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.

3. Solution in C++

int majorityElement(vector<int>& nums) {
    int count = 0;
    int candidate = 0;

    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

Explanation:

1. Use Boyer-Moore Voting Algorithm.

2. Initialize count and candidate.

3. Traverse the array: if count is 0, set the current element as candidate.

4. Increase count if the current element equals candidate, otherwise decrease count.

5. The remaining candidate after the loop is the majority element.

4. Solution in Java

public int majorityElement(int[] nums) {
    int count = 0;
    Integer candidate = null;

    for (int num : nums) {
        if (count == 0) {
            candidate = num;
        }
        count += (num == candidate) ? 1 : -1;
    }

    return candidate;
}

Explanation:

1. Implement the Boyer-Moore Voting Algorithm.

2. Start with a null candidate and count as 0.

3. Iterate over the array, changing candidate when count drops to 0.

4. Increment count for every match with candidate, otherwise decrement.

5. The candidate at the end is the majority element.

5. Solution in Python

def majorityElement(nums):
    count = 0
    candidate = None

    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1

    return candidate

Explanation:

1. Apply the Boyer-Moore Voting Algorithm.

2. Start with candidate as None and count as 0.

3. Loop through nums, changing candidate when count is 0.

4. Increment count if num matches candidate, else decrement.

5. The final value of candidate is the majority element.