Majority Element (n/3 times)

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

The LeetCode problem "Majority Element II" is a classic problem involving array manipulation and voting algorithms. The task is to find all elements in the given array that appear more than n/3 times, where n is the size of the array. Unlike the majority element problem where the threshold is n/2, in this variant, there can be up to two majority elements.

LeetCode link to the problem: Majority Element II.

Understanding the Problem

In this problem, you are given an integer array and your goal is to find all elements that appear more than one-third of the time. An element qualifies as a majority element if its count exceeds ⌊n/3⌋. One of the distinctive features of this problem is that it requires you to identify potentially multiple elements, not just a single majority element.

Example

Consider an array [3, 3, 4, 2, 4, 4, 2, 4]. Here, the elements that appear more than n/3 times is 4.

Key DSA Concepts and Theory

To effectively solve this problem, it's crucial to understand some foundational concepts:

Boyer-Moore Voting Algorithm

The Boyer-Moore Voting Algorithm is a powerful algorithm often used in majority element problems. Here, we extend it to handle the case where we're interested in elements appearing more than n/3 times. This refined approach can efficiently find potential candidates for majority elements, then confirm them if they exceed the required frequency count.

Solution Approach

The solution can be implemented by adapting the Boyer-Moore Voting Algorithm to accommodate two potential candidates due to the n/3 threshold. Here's a step-by-step breakdown:

  1. Initialize Candidates and Counters: We need to keep track of two potential majority candidates and their respective counters.

  2. First Pass - Candidate Identification: Iterate over the array to determine potential candidates by maintaining two counts. If the current element matches one of the candidates, increment the count. If either count is zero, assign the current element as a new candidate.

  3. Second Pass - Candidate Validation: Verify the identified candidates by iterating over the array again and counting the actual occurrences of these candidates to confirm if they genuinely appear more than n/3 times.

C++ Code Implementation

#include <vector>

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

    // First pass to find potential candidates
    int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;
    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 candidates
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
        if (num == candidate1) count1++;
        else if (num == candidate2) count2++;
    }

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

    return result;
}

Java Code Implementation

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length;
        if (n == 0) return new ArrayList<>();

        // First pass to find potential candidates
        int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;
        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 candidates
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == candidate1) count1++;
            else 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;
    }
}

Time and Space Complexity Analysis

  • Time Complexity: The algorithm runs in O(n) time. It traverses the array twice: once to identify potential candidates and a second time to confirm them.
  • Space Complexity: O(1) additional space is used since no extra data structures are required aside from a fixed number of counters and candidate variables.

Common Mistakes to Avoid

  • Confusing the factors 2 and 3 in modifications of the Boyer-Moore algorithm; ensure correctly handling two candidates and an n/3 threshold.
  • Forgetting to verify candidates in the second pass can lead to inaccurate results.

Similar Problems on LeetCode

Additional Resources and References