[Algorithm] Majority Elements I & II

Majority Elements:

Problem Statement:

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.

Solution 1: Bit checking

Time complexity: O(32N)Space complexity: O(32) or O(1)

Basic idea is to count occurrence of 1's in specific bit position. Each number is a 32 bit integer and if we look at the binary representation of it we can of course count the number of 1's occurrence in the entire array. Simply loop over the vector and count number of 1's at each 32 bit.

There are two flavors in this solution:

First one is to use the loop of bits as outer loop and use loop of vector as inner loop, and this has space complexity of O(1)

Second one is to use loop of vector as outer loop and use loop of bits as inner loop. This flavor has space complexity of O(32). We can also use score based counting instead of real counting, in other words, when we see 1 in the bit we ++count, else we --count.

Code for second flavor is as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: int majorityElement(vector<int>& nums) { vector<int> scores(32, 0); for (auto v : nums) { unsigned int mask = 0x1; for (int i=0; i<32; i++) { if (mask & v) { scores[i]++; } else { scores[i]--; } mask <<= 1; } } int result = 0; for (int i=0; i<32; i++) { if (scores[i] > 0) { result |= (1 << i); } } return result; } };

Solution 2: Championship solution

Time complexity: O(N)

Space complexity: O(1)

Time complexity of O(32n) of solution 1 is a bit annoying the constant factor is too big. Can we have something better, like O(n). The answer is yes.


In fact we can have a championship based solution. Imagine the majority means one number has occurrence of n/2 + 1 at least. And the count of others is n/2 at most. This leads to our championship based solution. We iterate over the vector, and for each number:

If there's no current champion, we make it our champion and set the score to be 1.
If there's one champion, we check:

        If the champion is the same as the value, we increment the score
        else we decrement the score and if the score reaches 0, we dethrone the champion


Finally we will have one champion left and that is our answer.

The code implemented as follows:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: int majorityElement(vector<int>& nums) { vector<pair<int, int> > scoreboard; for (auto v : nums) { if (scoreboard.empty()) { scoreboard.push_back(pair<int, int>(v, 1)); } else { pair<int, int>& champ = scoreboard.back(); if (champ.first == v) { champ.second++; } else { champ.second--; if (champ.second == 0) { scoreboard.pop_back(); } } } } return scoreboard.back().first; } };

Majority Elements II:

Problem description:

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

This is a variation of Majority Elements, this time we are asked to first elements occurring more than n/3 times. First off, let's think about how many elements occurring more than n/3 we will have at most.

The answer is 2. We can proof by contradiction:

Element One's occurrence: n/3 + 1Element Two's occurrence: n/3 + 1

If there's another element with occurrence n/3, the total number will be n + 2 which is a contradiction to total number of n.

Solution: Championship based, 2 winners.

Time complexity: O(n) (has a constant factor of 2)

Space complexity: O(1)

The solution is similar to the solution of championship solution. In our case we will have a maximum of two champions and the rules are also the same. We iterate over the vector, if there's slot for a champion, put the number into the winners list and set its score to 1. If there's no slot for a champion either increment the corresponding champion's score if the value is the same or challenge the champion by decrement their score (both of them). If any of the existing champions reaches 0 score, oust them.

Finally we are going to count the winners actual score and decide the majority number.

The code is implemented as following:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

class Solution { public: vector<int> majorityElement(vector<int>& nums) { int n = nums.size(); if (n == 0) return vector<int>(); vector<int> winners; vector<int> points; for (int i=0; i<n; i++) { int val = nums[i]; if (winners.size() == 0) { winners.push_back(val); points.push_back(1); } else if (winners.size() == 1) { if (winners.back() == val) { points.back()++; } else { winners.push_back(val); points.push_back(1); } } else if (winners.size() == 2) { if (winners[0] == val) { points[0]++; } else if (winners[1] == val) { points[1]++; } else { points[0]--; points[1]--; if (points[1] == 0) { points.pop_back(); winners.pop_back(); } if (points[0] == 0) { points.erase(points.begin()); winners.erase(winners.begin()); } } } else { assert(0); } } vector<int> results; for (int i=0; i<winners.size(); i++) { int temp = 0; for (int j=0; j<n; j++) { if (nums[j] == winners[i]) temp++; } if (temp > n/3) results.push_back(winners[i]); } return results; } };

Although we are using the vector here, the maximum we have is just two.