LeetCode Problem Link

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

Intuition

  • approach with simple solution: counting map 
          std::unordered_map<int, int> hashmap;
      for (int i=0; i<size(nums); ++i) {
          hashmap[nums[i]]++;
      }
      int max = 0;
      int major = -1;
      for (auto it=begin(hashmap);it!=end(hashmap);it++) {
          if (it->second > max) {
              max = it->second;
              major = it->first;
          }
      }
      return major;
  • Space Complexity \(O(N)\)

Approach

  • come up with an idea that kill both allies and enemies then we can start, as if, from the beginning!
  • use only two additional variables’ space, candidate and count (which can be decreased)

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(1)\)

Code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cand = 0;
        int cnt = 0;
        for (size_t i=0; i<size(nums); ++i) {
            if (cnt == 0) { cand = nums[i]; ++ cnt; }
            else if (cand == nums[i]) { ++cnt; }
            else { --cnt; }
        }
        return cand;
    }
};

GitHub

majority-element