0169.Majority Element

Link: 169. Majority Element - Easy
Track: Amazon tag

Question

Restate the problem

• Given nums, list of integers
• Return num, the element that appears more than ⌊n/2⌋ times (the majority element).
• The majority element is guaranteed to exist.

Edge Case

• if not nums, return something

---

Method 1 - hashmap
Method 2 - can improve to O(1)

Method 1 - Counter

Approach

• Use Counter to count the frequency of each number.
• Iterate through (num, freq) in the counter:
  • If freq > n // 2, return num.

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        n = len(nums)
        count = Counter(nums)
        for num, freq in count.items():
            if freq > n // 2:
                return num

Method 2 - O(1)

Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Code

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
                count = 1
            elif candidate != num:
                count -= 1
            elif candidate == num:
                count += 1
        
        return candidate

---

History

• Feb-06-2026 Peeked
  • don’t know method 2
• Feb-06-2026 Solved wo bug
  • did not consider edge case