169. Majority Element

Problem Statement:

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

Solution:
Algorithm:

• Initialize a HashMap with key and value as Integer.
• Iterate over the given input array.
• Adding elements to HashMap
• - If the element is already present in the HashMap, increment its count by 1
• - If the element is not present in the HashMap, add it to the HashMap with count 1
• Find the key with the highest value
• Iterate over the HashMap to find the key with the highest value
• If the value of the current key is greater than the value of the maxKey, update the maxKey
• Return the key with the highest value

Code:

public class Solution {
    public int majorityElement(int[] nums) {
        // 1. HashMap
        HashMap<Integer, Integer> map = new HashMap<>();
        //Adding elements to HashMap
        for (int i = 0; i < nums.length; i++) {
            // If the element is already present in the HashMap, increment its count by 1
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
            // If the element is not present in the HashMap, add it to the HashMap with count 1 
            else {
                map.put(nums[i], 1);
            }
        }
        // 2. Find the key with the highest value
        int max = 0;
        int maxKey = 0;
        // Iterate over the HashMap to find the key with the highest value
        for (Integer key : map.keySet()) {
            // If the value of the current key is greater than the value of the maxKey, update the maxKey
            if (map.get(key) > max) {
                max = map.get(key);
                maxKey = key;
            }
        }
        // Return the key with the highest value
        return maxKey;

    }

}