DEV Community

Cover image for 169. Majority Element
Harsh Rajpal
Harsh Rajpal

Posted on

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;

    }

}

Enter fullscreen mode Exit fullscreen mode

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more