Majority Element – Leetcode #169

Problem Statement

This problem is from Leetcode – 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.

Solution

This problem can easily be solved by pushing the integers in the given array into a Hashmap and keeping a count of how many time each integer has occurred in array. See the code sample below:

FirstApproach.java
public int majorityElement(int[] nums) {
        
		int majElem = nums[0];
		
		// compute the target count that we need to check
		double targetCount = (double)nums.length / 2;
		targetCount = Math.ceil(targetCount);
		
		// initialize a Hashmap - this will store integer and its count
		Map<Integer, Integer> numsCountMap = new HashMap<>();
		
		// Push given integers in it
		for(int i=0; i<nums.length; i++) {

			// if integer is pushed first time then keep value as 1
			if(!numsCountMap.containsKey(nums[i])) {

				numsCountMap.put(nums[i], 1);
			}
			// if integer already present then re-push after count increment
			else if(numsCountMap.containsKey(nums[i])) {
				
				int count = numsCountMap.get(nums[i]);
				count = count+1;
				numsCountMap.put(nums[i], count);
				
				// as soon as an integer with target count is encountered, return with the integer
				if(numsCountMap.get(nums[i]) >= targetCount) {
					
					return nums[i];
				}
			}

		}	
		
		return majElem;
    }

You can checkout the code from Github here – Majority Element

See the performance of this approach in terms of space complexity.