Majority Element

Problem Statement

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.

Examples

Example 1:

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

Example 2:

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

Approaches

1. Brute Force Approach

The brute force approach involves checking each element to see if it's the majority element by counting its occurrences.

Time Complexity: O(n^2) Space Complexity: O(1)

2. Optimal Approach (Boyer-Moore Voting Algorithm)

The optimal approach uses the Boyer-Moore Voting Algorithm to find the majority element in linear time and constant space.

Time Complexity: O(n) Space Complexity: O(1)

Solutions

Java Solution

// Brute Force Approach
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            if (count > n / 2) {
                return nums[i];
            }
        }
        return -1; // This line will never be reached if a majority element exists
    }
}

// Optimal Approach (Boyer-Moore Voting Algorithm)
class Solution {
    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;
    }
}

C++ Solution

// Brute Force Approach
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            if (count > n / 2) {
                return nums[i];
            }
        }
        return -1; // This line will never be reached if a majority element exists
    }
};

// Optimal Approach (Boyer-Moore Voting Algorithm)
class Solution {
public:
    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

Brute Force Approach

1. Iterate through each element in the array.
2. For each element, count its occurrences in the entire array.
3. If the count is greater than n/2, return that element as the majority element.

This approach is straightforward but inefficient for large arrays due to its O(n^2) time complexity.

Optimal Approach (Boyer-Moore Voting Algorithm)

The Boyer-Moore Voting Algorithm is based on the fact that if a majority element exists, it will remain the majority element in the array even after removing two different elements.

1. Initialize a count variable to 0 and a candidate variable to store the potential majority element.
2. Iterate through the array:
   • If count is 0, set the current element as the candidate.
   • If the current element is the same as the candidate, increment count; otherwise, decrement count.
3. The final value of candidate will be the majority element.

This algorithm works because the majority element appears more than n/2 times, so it will always have a positive count at the end, while all other elements will cancel out.

Test Cases

1. Input: [2,2,1,1,1,2,2] Output: 2 Explanation: The element 2 appears 4 times, which is more than 7/2 = 3 times.

2. Input: [3,3,4,2,4,4,2,4,4] Output: 4 Explanation: The element 4 appears 5 times, which is more than 9/2 = 4 times.

These test cases cover scenarios with odd and even array lengths, and different distributions of the majority element.