169. Majority Element

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

!!! info 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;
    }
}

Space Complexity

Time Complexity

\text{O}(n)

\text{O}(1)

# 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;
    }
}