169.Majority_Element_(Easy).md

169. Majority Element (Easy)

Date and Time: Jul 5, 2024, 13:22 (EST)

Link: https://leetcode.com/problems/majority-element/

Question:

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3, 2, 3]

Output: 3

Example 2:

Input: nums = [2, 2, 1, 1, 1, 2, 2]

Output: 2

Walk-through:

The solution uses Boyer–Moore algorithm with only two variables to keep track of the current majority element. We first initialize the curr to be i in nums if count = 0; otherwise, if i != curr we decrement curr's count until count is 0, we reassign curr to a new i; if i == curr, we increment count. In this way, we can always make sure the majority element

Python Solution:

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # Use a variable to keep track of current maximum elem
        # If i != curMax, decrement the count
        # If count == 0, update curMax to current eleme
        # Otherwise, increment the count

        # TC: O(n), SC: O(1)
        curMax, count = nums[0], 1
        for i in nums:
            if i != curMax:
                count -= 1
            else:
                count += 1
            if count == 0:
                curMax = i
                count += 1

        return curMax

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