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. Example 1:

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

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

JAVA
1class Solution {
2    public int majorityElement(int[] nums) {
3// Initialize the answer as -1 (assuming -1 means no majority element found)
4int ans = -1;
5
6// Create a frequency map to count occurrences of each number
7HashMap<Integer, Integer> freqMap = new HashMap<>();
8
9// Step 1: Count the frequency of each element in the array
10for (int x : nums) {
11    // If the element is not present, default count is 0, so increment by 1
12    freqMap.put(x, freqMap.getOrDefault(x, 0) + 1);
13}
14
15// Step 2: Iterate over the frequency map to find the element that occurs more than n/2 times
16for (Map.Entry<Integer, Integer> m : freqMap.entrySet()) {
17    // If frequency is greater than half the length of the array, it's the majority element
18    if (m.getValue() > nums.length / 2) {
19        ans = m.getKey(); // Store the majority element
20        break; // Majority element is unique, no need to continue
21    }
22}
23
24// Return the majority element (or -1 if not found)
25return ans;
26}
27}

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

Optimal Solution

JAVA
1class Solution {
2    public int majorityElement(int[] nums) {
3        // Initialize majority element with minimum integer value
4        int majEl = Integer.MIN_VALUE;
5        // Counter to keep track of the potential majority element
6        int cnt = 0;
7
8        // Iterate through each element in the array
9        for (int x : nums) {
10           // If counter is 0, assume the current element as the majority element
11           if (cnt == 0) {
12                majEl = x;
13                cnt++;
14            }
15            // If the current element is same as the assumed majority element, increment the counter
16            else if (majEl == x) {
17                cnt++;
18            }
19            // If the current element is different, decrement the counter
20            else {
21                cnt--;
22            }
23        }
24
25        // majEl will be the majority element at the end of iteration
26        return majEl;
27    }
28}
29