169. Majority Element

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

Problem

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

Solution

1. $O(N)$ Space using Hash Map

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> count_of;
        for (const auto &n : nums) count_of[n]++;
        for (const auto &pair: count_of) {
            if (pair.second > nums.size() / 2) return pair.first;
        }
        return -1;
    }
};

2. $O(1)$ Space

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = -1;
        int count = 0;
        for (const auto &n : nums) {
            if (count == 0) ans = n;
            if (ans == n) count++;
            else count--;
        }
        return ans;
    }
};

• #hash

• #math