Leetcode — Top Interview 150–169. Majority Element

It’s an easy problem with the description being:

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 * 104
-109 <= nums[i] <= 109

At first glance you would think about making a map then gathering the one that shows most.

On second thought if you could sort and get the one that shows up most that would do.

And with that there is even a simpler way. If you read carefully the description you would understand that a majority element is one that appears more than half of the array.

With that in mind, if you would sort it and grab the index of middle, that would solve the issue:

class Solution {
    public int majorityElement(int[] nums) {

        // sort
        Arrays.sort(nums);

        // if by majority element it means that appears more than half of nums size
        // then picking the middle element would be the one that's a majority element
        return nums[nums.length / 2];
    }
}

Runtime: 4 ms, faster than 54.53% of Java online submissions for Majority Element.

Memory Usage: 53.5 MB, less than 9.23% of Java online submissions for Majority Element.

—

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)

Comments

[Boopathi]

This is a clever solution! I like how you highlighted the key insight that the majority element is simply the middle element after sorting.