Skip to main content

Majority Element II

Problem

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

Examples

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 * 10^4
  • -10^9 <= nums[i] <= 10^9

Approach

To solve this problem, we can use the Boyer-Moore Voting Algorithm, which efficiently finds the majority elements in linear time and constant space. The algorithm can be summarized in the following steps:

  1. First Pass:

    • Use two counters and two candidate variables to identify the potential majority elements.
    • Iterate through the array, updating the candidates and their counts accordingly.
  2. Second Pass:

    • Verify the candidates by counting their occurrences in the array.

Solution

Code in Different Languages

C++ Solution

#include <vector>
#include <iostream>

using namespace std;

vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
if (n == 0) return {};

int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;

// First pass to find potential candidates
for (int num : nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}

// Second pass to confirm the candidates
count1 = count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
if (num == candidate2) count2++;
}

vector<int> result;
if (count1 > n / 3) result.push_back(candidate1);
if (count2 > n / 3) result.push_back(candidate2);

return result;
}

int main() {
vector<int> nums = {3,2,3};
vector<int> result = majorityElement(nums);
for (int num : result) {
cout << num << " ";
}
}

Java Solution

import java.util.*;

public class MajorityElementII {
public static List<Integer> majorityElement(int[] nums) {
int n = nums.length;
if (n == 0) return Collections.emptyList();

int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;

// First pass to find potential candidates
for (int num : nums) {
if (num == candidate1) {
count1++;
} else if (num == candidate2) {
count2++;
} else if (count1 == 0) {
candidate1 = num;
count1 = 1;
} else if (count2 == 0) {
candidate2 = num;
count2 = 1;
} else {
count1--;
count2--;
}
}

// Second pass to confirm the candidates
count1 = count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
if (num == candidate2) count2++;
}

List<Integer> result = new ArrayList<>();
if (count1 > n / 3) result.add(candidate1);
if (count2 > n / 3) result.add(candidate2);

return result;
}

public static void main(String[] args) {
int[] nums = {3, 2, 3};
List<Integer> result = majorityElement(nums);
System.out.println(result);
}
}

Python Solution

def majorityElement(nums):
n = len(nums)
if n == 0:
return []

candidate1, candidate2, count1, count2 = 0, 1, 0, 0

# First pass to find potential candidates
for num in nums:
if num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1
elif count1 == 0:
candidate1 = num
count1 = 1
elif count2 == 0:
candidate2 = num
count2 = 1
else:
count1 -= 1
count2 -= 1

# Second pass to confirm the candidates
count1, count2 = 0, 0
for num in nums:
if num == candidate1:
count1 += 1
elif num == candidate2:
count2 += 1

result = []
if count1 > n / 3:
result.append(candidate1)
if count2 > n / 3:
result.append(candidate2)

return result

nums = [3, 2, 3]
print(majorityElement(nums))

Complexity Analysis

Time Complexity: O(N)

Reason: We perform two passes through the array, each requiring linear time.

Space Complexity: O(1)

Reason: We use a constant amount of extra space for counters and candidates.

This solution efficiently finds all elements that appear more than ⌊ n/3 ⌋ times using the Boyer-Moore Voting Algorithm. The time complexity is linear, and the space complexity is constant, making it suitable for large input sizes.

References

LeetCode Problem: Majority Element II Authors GeeksforGeeks Profile: Vipul lakum