# 229. Majority Element II

Description:

https://leetcode.com/problems/majority-element-ii/#/description

Algorithm:

Traverse the array for 2 times.

The first pass:

Use two candidate to record the most recent words.

• if nums[i] == candidate, count++
• if nums[i] != candidate, count–

The second pass:
Check the number of appearance of the candidates.

Code:
``` class Solution { public: vector<int> majorityElement(vector<int>& nums) { int candidate1 = INT_MIN, candidate2 = INT_MIN; int count1 = 0, count2 = 0; for (int i = 0; i < nums.size();i++) { if (nums[i] == candidate1) count1++; else if (nums[i] == candidate2) count2++; else if (count1 == 0) { candidate1 = nums[i]; count1 = 1; } else if (count2 == 0) { candidate2 = nums[i]; count2 = 1; } else { count1--; count2--; } } count1 = 0; count2 = 0; for (int i = 0; i < nums.size();i++) { if (nums[i] == candidate1) count1++; else if (nums[i] == candidate2) ``````// Here it must be else if rather than if. If the array = {INT_MIN}, candidate1 and candidate2 would both be INT_MIN. And if you use if here, the word will be counted for two times. count2++; } vector <int> result; if (count1 > nums.size() / 3) result.push_back(candidate1); if (count2 > nums.size() / 3) result.push_back(candidate2); return result; } };```

Timing & Space:

O(n) & O(1)