LeetCode //C - 229. Majority Element II

229. Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
 

Example 1:

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

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

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

Constraints:

• $1<=nums.length<=5\ast 10^4$
• $-10^9<=nums[i]<=10^9$

From: LeetCode
Link: 229. Majority Element II

---

Solution:

Ideas:

1. Initialization: We initialize two candidates with any two different values and their counts to 0. This ensures that our algorithm doesn’t falsely initialize both candidates to the same value.

2. First Pass: We iterate through the array to find up to two potential candidates for the majority elements.

• If the current element matches one of the candidates, we increment its count.
• If the current element does not match either candidate and one of the counts is zero, we update that candidate and reset its count.
• If the current element does not match either candidate and both counts are non-zero, we decrement both counts.

3. Second Pass: We verify if the candidates we found in the first pass actually appear more than ⌊n/3⌋ times.
4. Result Construction: We construct the result array with the verified candidates.

Code:

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* majorityElement(int* nums, int numsSize, int* returnSize) {if (numsSize == 0) {*returnSize = 0;return NULL;}int candidate1 = 0, candidate2 = 1; // Initialize candidates to any two different valuesint count1 = 0, count2 = 0;// 1st pass: find potential candidatesfor (int i = 0; i < numsSize; 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--;}}// 2nd pass: verify candidatescount1 = 0;count2 = 0;for (int i = 0; i < numsSize; i++) {if (nums[i] == candidate1) {count1++;} else if (nums[i] == candidate2) {count2++;}}int* result = (int*)malloc(2 * sizeof(int));*returnSize = 0;if (count1 > numsSize / 3) {result[*returnSize] = candidate1;(*returnSize)++;}if (count2 > numsSize / 3) {result[*returnSize] = candidate2;(*returnSize)++;}return result;
}