Skip to content
AI360Xpert
Back to Arrays & Hashing
Easy

Majority Element

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

Input:nums = [3,2,3]
Output:3
3 appears 2 times, which is more than 3/2 = 1.5 times.
Input:nums = [2,2,1,1,1,2,2]
Output:2
2 appears 4 times, which is more than 7/2 = 3.5 times.

Constraints

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

Approach

Iterate through the array and count the frequencies of each element using a hash map. At the same time, keep track of the element with the maximum frequency. If any element's frequency exceeds n/2, return it.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(n)

This approach requires O(n) space to store the frequencies.

Solution.java
class Solution {    public int majorityElement(int[] nums) {        Map<Integer, Integer> map = new HashMap<>();        int majorityCount = nums.length / 2;                for (int num : nums) {            int count = map.getOrDefault(num, 0) + 1;            if (count > majorityCount) {                return num;            }            map.put(num, count);        }                return -1; // Should not reach here    }}