Find the element which appears more than half the array size

Given an array, find the majority element which appears more than half the size of the array.

Constraints:

  • There is only one such element and it always exists.
  • Time complexity should be O(n)
  • Space complexity should be O(1)

For example,

in the below array:

[7,6,8,7,7,7]

The output is 7 since it appears 4 times which is more than half the size of the array (3)

Solution:

Finding a solution with O(n) extra space is easier.

We will look at them first before finding optimized solution.

Approach 1 – Using HashMap:

you can maintain a map with each value and its number of occurences.

Finally you can scan through the map and return the element which has more count than half the array size.

class Solution {
    public int majorityElement(int[] nums) {
        
        
        Map<Integer,Integer> m = new HashMap<>();
        
        for(int i:nums){
            
            
            
                
                m.put(i,m.getOrDefault(i,0)+1);
            
        }
        
        
        
        
        for(int k:m.keySet()){
            
            
            if(m.get(k) > nums.length/2) return k;
        }
        
        return 0;
    }
}

Time complexity:

Time complexity is O(2n) once for finding the frequency and then for finding the key with highest frequency.

Removing the constant it is equal to O(n)

Space complexity :

We use an extra map of size n , so space complexity is O(n)

Approach 2 – By sorting:

Once you sort the given array you can just return the middle element.

This is because since we are looking for an element which occurs more than half the size of the array , the middle element will definitely be that element.

here is the code:

class Solution {
    public int majorityElement(int[] nums) {
        
        
        Arrays.sort(nums);
        
        return nums[nums.length/2];
        
    }
}

We dont use extra space here , so space complexity is O(1)

But the time complexity is O(nlogn) since we do sorting.

Approach 3 – Boyer Moore Voting Algorithm

Boyer Moore Voting algorithm provides an optimized solution with time complexity O(n) and without using extra space in proportion to the input.

here is the algorithm:

  • We will use a counter with an initial value of 0
  • Scan through each element in the array and do the following:
    • If count value is zero assign the current element as the candidate element (element we want to return finally)
    • If the candidate value and the current value are the same increment the counter
    • If candidate and current values are not same decrement the counter
  • Return the candidate element

here is the code:

class Solution {
    public int majorityElement(int[] nums) {
        
        
        int candidate = 0;
        int count = 0;
        for(int i:nums){
            
            
            
            if(count == 0){
                
                candidate = i;
            }
            
            count += (i == candidate)? 1: -1; 
        }
        
        
        return candidate;
        
    }
}

That’s it!

Comments

Leave a Reply

Discover more from The Full Stack Developer

Subscribe now to keep reading and get access to the full archive.

Continue reading