Problem 35 - Majority Element

Explore our archive for previous posts.

Problem 34 - Interleaving String

Problem 33 - Edit Distance

Question

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.

Example 1:

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

Example 2:

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

Constraints:

• n == nums.length

• 1 <= n <= 5 * 10^4

• -10^9 <= nums[i] <= 10^9

Approach

This solution uses the Boyer-Moore Voting Algorithm to find the majority element efficiently. It relies on the fact that if you cancel out each occurrence of different elements with occurrences of the majority element, the majority element will still remain (since majority element occurs more than half of the times of the total array length).

Here's a simplified explanation:

1. Start with a candidate element as the majority element.

2. Iterate through the array:

   • If the current element matches the candidate, increment a count.

   • If the current element doesn't match the candidate, decrement the count.

3. Whenever the count becomes zero, it means that you've canceled out equal occurrences of different elements. In this case, update the candidate to the current element and reset the count to 1.

4. After processing the entire array, the candidate element left is highly likely to be the majority element.

This algorithm works because the majority element occurs more than n/2 times, so it can cancel out all other elements and still be the majority.

It's a clever way of finding the majority element without explicitly storing counts for each element, making it an efficient solution.

Solution

Solve it here

class Solution {
    public int majorityElement(int[] nums) {
        // Consider first element as majority element candidate
        int candidate = nums[0];
        int count = 1; 

        for (int i = 1; i < nums.length; i++) {
            // Increment count of majority element occurrence
            if (nums[i] == candidate) {
                count++;
            } else {
                // Decrement count of majority element occurrence
                count--;

                // Potential new majority element candidate
                if (count == 0) {
                    candidate = nums[i];
                    count = 1;
                }
            }
        }

        // At the end, 'candidate' holds the majority element.
        return candidate;
    }
}

Time and space complexity

Time Complexity: The algorithm makes a single pass through the array, so the time complexity is O(n), where n is the size of the array.

Space Complexity: The algorithm uses constant extra space, so the space complexity is O(1).

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Want free mock interviews?

Simply share our newsletter with your friends, colleagues, or anyone you think would love our coding insights.

When your friends use your referral link to subscribe, you’ll receive special benefits.

• Get a free mock coding interview for 10 referrals

• Get a 1:1 coding Q&A session for 15 referrals

• Get a guest post opportunity for 25 referrals