DEV Community

Cover image for Leetcode — Top Interview 150–169. Majority Element
Ben Pereira
Ben Pereira

Posted on

1

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];
    }
}
Enter fullscreen mode Exit fullscreen mode

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! :)

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (1)

Collapse
 
programmerraja profile image
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.

Speedy emails, satisfied customers

Postmark Image

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up