Vultr DocsLatest Content

Majority Element II

Updated on 12 June, 2025
Majority Element II header image

Problem Statement

In this given task, we need to identify all the unique elements within an integer array which have a frequency exceeding one third of the size of the array. More specifically, for an array of size n, any element that appears more than ⌊ n/3 ⌋ times should be captured. This involves counting occurrences of each array element and comparing these counts to the threshold calculated as the floor division of n by three.

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 * 104
  • -109 <= nums[i] <= 109

Approach and Intuition

The challenge primarily revolves around efficient frequency computation and comparison with the ⌊ n/3 ⌋ threshold. Below are steps and thoughts towards achieving the solution:

  1. Calculate the threshold ⌊ n/3 ⌋. This represents the minimum number of times an element must appear in the array to be considered as "more frequent than a third".

  2. Use an efficient way to count the occurrences of each element in the array. Several approaches can be used here:

    • Hashing: Utilize a hash map to keep track of the count of each element. This is straightforward and efficient with a time complexity of O(n).
    • Moore's Voting Algorithm Variant: This algorithm is typically used to find elements that appear 'more than n/k' times. For this problem, where k is fixed as 3, an adaptation of Moore’s Voting can be used.

  3. After getting the frequency counts, another pass can be made through the hash map (or an accumulated list from Moore’s algorithm) to collect all elements that meet or exceed the threshold ⌊ n/3 ⌋.

  4. Return these elements as the result. The output format may vary: often, as a list. The solution must ensure the results are unique elements, each of which complies with the specified frequency condition.

This approach ensures that all constraints are respected and follows a methodological pattern to solve within acceptable complexities, both temporal and spatial, as defined in the problem's constraints.

Solutions

  • Java
  • Python
java 
class Solution {
    public List<Integer> findMajorityElements(int[] nums) {
        int freq1 = 0;
        int freq2 = 0;
        Integer major1 = null;
        Integer major2 = null;

        for (int num : nums) {
            if (major1 != null && num == major1) {
                freq1++;
            } else if (major2 != null && num == major2) {
                freq2++;
            } else if (freq1 == 0) {
                major1 = num;
                freq1 = 1;
            } else if (freq2 == 0) {
                major2 = num;
                freq2 = 1;
            } else {
                freq1--;
                freq2--;
            }
        }

        List<Integer> finalResult = new ArrayList<>();
        
        freq1 = 0;
        freq2 = 0;

        for (int num : nums) {
            if (major1 != null && num == major1) freq1++;
            if (major2 != null && num == major2) freq2++;
        }

        int threshold = nums.length / 3;
        if (freq1 > threshold) finalResult.add(major1);
        if (freq2 > threshold) finalResult.add(major2);

        return finalResult;
    }
}

The provided Java solution aims to identify elements in an array nums that appear more than n/3 times, where n is the size of the array. This approach revolves around the idea of tracking potential majority elements using a variation of the Boyer-Moore Voting Algorithm, specifically designed to handle the scenario of finding all elements that appear more than n/3 times.

Here's a breakdown of the algorithm implemented in the code:

  • First, initialize two candidate elements (major1 and major2) along with their respective frequencies (freq1 and freq2).

  • Iterate through each number in the array nums:

    • If the current number matches major1, increase freq1.
    • If it matches major2, increase freq2.
    • If freq1 is zero, propose the current element as a new candidate for major1 and reset freq1.
    • Similarly, propose a new candidate for major2 if freq2 is zero.
    • If the current number matches neither major1 nor major2, decrease both freq1 and freq2.

  • After proposing potential majority candidates, reset the frequencies and reiterate through the array to confirm the actual counts of major1 and major2.

  • For each valid candidate (those that meet the n/3 threshold), add it to the result list finalResult.

Note that this solution ensures that only the elements which truly appear more than n/3 times get added to finalResult. This operation has a time complexity of O(n) due to two linear passes over the dataset and a constant space complexity, owing to the storage of a few variables. Thoroughly analyze this method to understand the efficiency of the modified Boyer-Moore Voting Algorithm in handling variations of majority element problems.

python 
class Solution:

    def findMajorElements(self, elements):
        if not elements:
            return []
        
        first_count, second_count, first_candidate, second_candidate = 0, 0, None, None
        for el in elements:
            if first_candidate == el:
                first_count += 1
            elif second_candidate == el:
                second_count += 1
            elif first_count == 0:
                first_candidate = el
                first_count = 1
            elif second_count == 0:
                second_candidate = el
                second_count = 1
            else:
                first_count -= 1
                second_count -= 1
        
        final_results = []
        for candidate in [first_candidate, second_candidate]:
            if elements.count(candidate) > len(elements) // 3:
                final_results.append(candidate)

        return final_results

The provided solution in Python addresses the problem of identifying elements in a list that appear more than n/3 times, where n is the size of the list. The approach used is an efficient algorithm known as "Boyer-Moore Voting Algorithm". Below is an outline of the steps and logic applied in the code:

  1. Initialize counters and candidates for the two potential majority elements. These handle the tracking of elements that could possibly have the required frequency.

  2. Iterate through each element in the list:

    • Increment the count if the current element matches one of the candidates.
    • If the count for a candidate is zero, assign the current element as the new candidate and set its count to one.
    • If the element does not match any current candidate and counts are not zero, decrement the counts for both candidates.

  3. After identifying possible candidates, validate whether these candidates actually appear more than n/3 times by counting their occurrences in the list.

  4. Return a list of validated candidates.

This method ensures optimal performance, processing the list in linear time and using constant space. Remember to check edge cases such as empty lists or lists where no majority element exists, as the handling of these is crucial for robust implementation.

Comments

No comments yet.