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
- The input is generated such that a majority element will exist in the array.
My Solution
We can solve this by maintaining the count of each element in a HashMap. Once the count of a number exceeds n/2, we return that number.
Time complexity would be O(n) because we iterate through the array once. Space complexity would also be O(n) to maintain the HashMap.
class Solution {
public int majorityElement(int[] nums) {
int n = nums.length;
Map<Integer,Integer> counts = new HashMap<>();
for (int num : nums) {
counts.put(num, counts.getOrDefault(num,0)+1);
if (counts.get(num) > (n/2)) {
return num;
}
}
return -1;
}
}