Majority Element

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given an array, find the element that appears majority of the time
• Majority means more than $n/2$ times

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Uses Boyer-Moore Voting algorithm
• Guaranteed that answer exists

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Maintain a count and a candidate
• If count is zero that means we are looking for a new candidate
• If current number is candidate then count += 1
• Else count -= 1

Why This Works

(Explain the core reason the solution is correct.)

• You cancel out the count of numbers and if guaranteed that an answer exists then you cannot cancel out the answer
• 2, 2, 1, 1, 2 -> will cancel the two 2s then 1s, remaining will be the final 2

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Boyer-Moore Voting

Time & Space Complexity

• Time: O($n$) → Reason: Iterating through the array once
• Space: O($1$) → Reason: Not storing anything except some variables

Code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0: # find new candidate
                candidate = num
                count += 1  
            elif candidate == num:
                count += 1
            else: # cancel out the count
                count -= 1
        return candidate

Common Mistakes / Things I Got Stuck On

• I was forgetting to increment the count when selecting a new candidate

if count == 0: # find new candidate
	candidate = num
	count += 1 # THIS HERE or count = 1