Majority Element – Leetcode #169

Problem Statement

This problem is from Leetcode – Majority Element.

Given an array nums, return the element that appears more than half the time. Assume such an element always exists.

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:

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.

PERFORMANCE ANALYSIS

RUNTIME	23 ms | Beats 8.05 %
MEMORY	48.87 MB | Beats 95.07 %
TIME COMPLEXITY	O (N)