algoadvance

Leetcode 229. Majority Element II

Problem Statement

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:

Clarifying Questions

  1. Can the array be empty?
    • No, per the constraint, the array will have at least one element.
  2. Should the output be in any specific order?
    • The problem does not specify an order, so any order is acceptable.
  3. Can I use extra space for this problem?
    • The problem does not explicitly constrain space, but an efficient solution using constant space is preferred.

Strategy

To solve this problem, we can use a modified version of the Boyer-Moore Voting Algorithm which is originally used for finding the majority element (i.e., an element that appears more than ⌊ n/2 ⌋ times). For this problem, we need to find elements that appear more than ⌊ n/3 ⌋ times.

Key steps are:

  1. First Pass: Use the Boyer-Moore Voting Algorithm to find up to 2 candidate elements that could be the majority elements.
  2. Second Pass: Verify the count of each of these candidates to determine if they actually appear more than ⌊ n/3 ⌋ times.

Code

#include <vector>
#include <unordered_map>
using namespace std;

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

    int candidate1 = 0, candidate2 = 1; // Initialize two different candidates
    int count1 = 0, count2 = 0;

    // First pass to find possible 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 check if the candidates actually have the required count
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
        if (num == candidate1) {
            count1++;
        } else 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;
}

Time Complexity

The solution involves two passes through the array:

  1. First Pass: Identifying candidates takes O(n) time, where n is the length of the array.
  2. Second Pass: Counting the occurrences of the candidates also takes O(n) time.

Overall, the time complexity is O(n).

The space complexity is O(1) because we use a constant amount of extra space beyond the input array.

This solution is efficient and meets the constraints specified in the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI