169. Majority Element

#array #moores_voting_algorithm

Given an array find the element that appears more than $\frac{n}{2}$ times ( assume such majority element always exists in the array )

Solve this problem in linear time $\text{O}(n)$ using constant space

Intuition

• We can use the simple voting mechanism where anything different is considered a vote against.

  • Only the majority element will have vote in his favour.

Approach

• Track the candidate & the number of vote i.e its occurrence.

  • If we encounter an element different from the candidate decrease the vote count

  • If for the current candidate the votes become 0 replace it

• At the end only the max occurring element will remain.

Complexity

Space Complexity	Time Complexity
$\text{O}(n)$	$\text{O}(1)$

• No extra space is needed

Code

class Solution {
    public int majorityElement(int[] nums) {
    
        // we count the votes 
	// number of votes will be > 0 only for the majority element
        int count = 1, candidate = nums[0];
        
        for (int i = 1; i < nums.length; ++i) {
            if(nums[i] == candidate) {
                count++;
            } else {
            	// if the element is different consider it as vote againts 
                count--;
                // if votes is 0 then replace the candiate
                if(count == 0) {
                    candidate = nums[i];
                    count = 1;
                }
                
            }
        }

        

        return candidate;
    }
}