229. Majority Element II

MediumArrayHash TableCountingSorting
Leetcode Link

Problem Description

The given problem requires determining all the elements in an integer array of size n that appear more than ⌊ n/3 βŒ‹ times. This threshold implies that we need to find elements which are present in significant quantities, enough to surpass a third of the array's total size. The output should be a list of these dominant elements, and it is implied that the list could include zero, one, or two elements since it's not possible to have more than two elements that each appear more than ⌊ n/3 βŒ‹ times in the same array.

Intuition

The solution approach stems from a voting algorithm, specifically an extension of the Boyer-Moore Majority Voting algorithm. The original algorithm is designed to find a majority element in an array which appears more than half of the time. In this extended problem, we are looking for elements which appear more than a third of the time, so the array can have at most 2 such elements.

Here is the thinking process broken down:

  1. We initiate two potential candidates for the majority element, m1 and m2, with placeholders that don't match any elements in the array to start with. These candidates represent the two elements we think might be appearing more than ⌊ n/3 βŒ‹ times.

  2. Similarly, we have two counters, n1 and n2, that help us keep track of the number of times we have encountered m1 and m2 in the array.

  3. We iterate through the array (nums). For each element (m), we do the following:

    • If m is equal to one of our current candidates (m1 or m2), we increment the respective counter (n1 or n2).
    • If one of the counters is at zero, it means the respective candidate is not a valid majority element or has been 'voted out', so we replace it with the current element m and set its counter to 1.
    • If m is not matching either candidate and both counters n1 and n2 are not zero, we decrement both counters. This is analogous to 'voting out' a candidate, as there must be at least three distinct numbers in the current sequence (thus each couldn't be more than ⌊ n/3 βŒ‹ appearances).
  4. Since the counters can be manipulated by elements that are not actually the desired majority elements, we make a final pass through the array to check whether our candidates truly occur more than ⌊ n/3 βŒ‹ times. We construct the result list by only including candidates that meet this criterion.

This intuition behind the algorithm leverages the idea that if we cancel out triples of distinct elements, any element that appears more than a third of the time will still remain.

Learn more about Sorting patterns.

Solution Approach

The solution code provided implements the approach discussed in the intuition section. Let's walk through the implementation.

  1. We initialize two counters n1 and n2 to zero. These counters will track the number of times we 'see' each candidate.

  2. Similarly, we start with two candidate variables m1 and m2. Values don't matter as long as they're different from each other, hence they're initialized to 0 and 1 respectively.

  3. Then, we iterate over all the elements m of the input array nums and apply the Boyer-Moore Voting algorithm, extended to find elements occurring more than ⌊ n/3 βŒ‹ times:

    • If m is equal to one of our candidates (m1 or m2), we increase the corresponding counter (n1 or n2).
    • If m is not equal to either candidate and one of the counters is zero, we set that candidate to m and reset its counter to 1. This signifies that we are considering a new element as a potential majority candidate.
    • If m is different from both of the existing candidates and both counters are not zero, we decrease both counters. This represents a 'vote out' scenario where we discard a 'set' of three different elements.
  4. After the loop, we have two candidates m1 and m2. However, these are only potential majority elements because their counters may have been falsely increased by elements that are not actual majorities.

  5. To ensure that our candidates are valid, we perform a final pass through the array:

    • We build a new list by including the candidates that actually occur more than ⌊ n/3 βŒ‹ times by using the .count() method.
  6. The final result consists of this list, which contains zero, one, or two elements occurring more than ⌊ n/3 βŒ‹ times in the array.

The implementation effectively uses constant space, with only a few integer variables, and linear time complexity, since we make a constant number of passes over the array. The voting algorithm is an elegant solution for such majority element problems, and its extension allows it to be used even with different occurrence thresholds.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider an example array nums = [1, 2, 3, 1, 1, 2, 1]. This array has a size n = 7, so we are looking for elements that appear more than ⌊ n/3 βŒ‹ = ⌊ 7/3 βŒ‹ = 2 times.

Here's a step-by-step breakdown of how the algorithm would process this example:

  1. We initiate two counters n1 and n2 and set them to zero. These will track occurrences of our candidates. We also start with two variables for the candidates m1 and m2, initializing them to 0 and 1, respectively.

  2. We begin iterating over the elements of nums:

    • Iteration 1: m = 1. Neither m1 nor m2 is set to 1, and since n1 is zero, we update m1 to 1 and n1 to 1.
    • Iteration 2: m = 2. m is not equal to m1 or m2, and n2 is zero, so we update m2 to 2 and n2 to 1.
    • Iteration 3: m = 3. m matches neither m1 nor m2, and both counters are not zero, so we decrease both n1 and n2 by 1.
    • Iteration 4: m = 1. m matches m1, so we increase n1 to 1 (n1 was decreased in the last step).
    • Iteration 5: m = 1. m matches m1, so we increase n1 to 2.
    • Iteration 6: m = 2. m matches m2, so we increase n2 to 1 (it was decreased earlier).
    • Iteration 7: m = 1. m matches m1, so n1 becomes 3.
  3. After the first pass, n1 and n2 count 3 and 1 respectively. Our candidates are m1 = 1 and m2 = 2.

  4. We need to confirm our candidates' actual occurrences with a second pass:

    • m1 = 1 appears 4 times in nums, which is more than 2 (⌊ n/3 βŒ‹).
    • m2 = 2 appears 2 times, which equals ⌊ n/3 βŒ‹ but does not exceed it.
  5. Only m1 passed the final verification, which means 1 appears more than ⌊ n/3 βŒ‹ times in the array.

  6. The result list contains a single element [1], which is the element occurring more than ⌊ n/3 βŒ‹ times in nums.

Through the approach described in the solution above, we efficiently determined the elements that satisfy the required occurrence condition with this example.

Solution Implementation

1from typing import List
2
3class Solution:
4    def majorityElement(self, nums: List[int]) -> List[int]:
5        # Initialize two potential majority elements and their respective counters.
6        candidate1, candidate2 = None, None
7        count1, count2 = 0, 0
8      
9        # Perform Boyer-Moore Majority Vote algorithm
10        for num in nums:
11            # If the current element is equal to one of the potential candidates,
12            # increment their respective counters.
13            if num == candidate1:
14                count1 += 1
15            elif num == candidate2:
16                count2 += 1
17            # If one of the counters becomes zero, replace the candidate with
18            # the current element and reset the counter to one.
19            elif count1 == 0:
20                candidate1, count1 = num, 1
21            elif count2 == 0:
22                candidate2, count2 = num, 1
23            # If the current element is not equal to any candidate and both
24            # counters are non-zero, decrement both counters.
25            else:
26                count1 -= 1
27                count2 -= 1
28      
29        # Check whether the candidates are legitimate majority elements.
30        # A majority element must appear more than len(nums) / 3 times.
31        return [m for m in (candidate1, candidate2) if nums.count(m) > len(nums) // 3]
32
1import java.util.List;
2import java.util.ArrayList;
3
4class Solution {
5    public List<Integer> majorityElement(int[] nums) {
6        // Initialize the two potential majority elements and their counters
7        int major1 = 0, major2 = 0; 
8        int count1 = 0, count2 = 0;
9
10        // First pass: find the two majority element candidates
11        for (int num : nums) {
12            if (num == major1) {
13                // If the current element is equal to the first candidate, increment its counter
14                count1++;
15            } else if (num == major2) {
16                // If the current element is equal to the second candidate, increment its counter
17                count2++;
18            } else if (count1 == 0) {
19                // If the first candidate's count is zero, select the current element as the first candidate
20                major1 = num;
21                count1 = 1;
22            } else if (count2 == 0) {
23                // If the second candidate's count is zero, select the current element as the second candidate
24                major2 = num;
25                count2 = 1;
26            } else {
27                // If the current element is not equal to either candidate, decrement both counters
28                count1--;
29                count2--;
30            }
31        }
32
33        // Second pass: validate the candidates
34        List<Integer> result = new ArrayList<>();
35        count1 = 0;
36        count2 = 0;
37
38        // Count the actual occurrences of the candidates in the array
39        for (int num : nums) {
40            if (num == major1) {
41                count1++;
42            } else if (num == major2) {
43                count2++;
44            }
45        }
46
47        // Check if the candidates are majority elements (> n/3 occurrences)
48        if (count1 > nums.length / 3) {
49            result.add(major1);
50        }
51        if (count2 > nums.length / 3) {
52            result.add(major2);
53        }
54
55        // Return the list of majority elements
56        return result;
57    }
58}
59
1#include <vector>
2#include <algorithm> // Include algorithm header for count function
3
4class Solution {
5public:
6    std::vector<int> majorityElement(std::vector<int>& nums) {
7        int count1 = 0, count2 = 0;     // Initialize counters for two potential majority elements
8        int candidate1 = 0, candidate2 = 1; // Initialize holders for two potential majority elements
9      
10        // Use Boyer-Moore Voting Algorithm to find potential majority elements
11        for (int num : nums) {
12            if (num == candidate1) {
13                // If the current element is the same as candidate1, increment count1
14                ++count1;
15            } else if (num == candidate2) {
16                // If the current element is the same as candidate2, increment count2
17                ++count2;
18            } else if (count1 == 0) {
19                // If count1 is 0, replace candidate1 with the current element and reset count1
20                candidate1 = num;
21                count1 = 1;
22            } else if (count2 == 0) {
23                // If count2 is 0, replace candidate2 with the current element and reset count2
24                candidate2 = num;
25                count2 = 1;
26            } else {
27                // If the current element is not equal to either candidate and both counts are non-zero, decrement both counts
28                --count1;
29                --count2;
30            }
31        }
32      
33        std::vector<int> result; // Initialize an empty result vector
34        // Check if the candidates are indeed majority elements
35        if (std::count(nums.begin(), nums.end(), candidate1) > nums.size() / 3) {
36            // If candidate1's occurrence is more than a third of the array length, add to the result
37            result.push_back(candidate1);
38        }
39        if (candidate1 != candidate2 && std::count(nums.begin(), nums.end(), candidate2) > nums.size() / 3) {
40            // If candidate2 is different from candidate1 and occurs more than a third of the array length, add to the result
41            // Check candidate1 != candidate2 to avoid counting the same element twice in case of duplicates
42            result.push_back(candidate2);
43        }
44      
45        return result; // Return the final result
46    }
47};
48
1function majorityElement(nums: number[]): number[] {
2    // Initialize counters for two potential majority elements
3    let count1: number = 0;
4    let count2: number = 0;
5    // Initialize placeholders for two potential majority elements
6    let candidate1: number = nums[0] || 0;
7    let candidate2: number = nums[1] || 1;
8  
9    // Use Boyer-Moore Voting Algorithm to find potential majority elements
10    for (let num of nums) {
11        if (num === candidate1) {
12            // If the current element is the same as candidate1, increment count1
13            count1++;
14        } else if (num === candidate2) {
15            // If the current element is the same as candidate2, increment count2
16            count2++;
17        } else if (count1 === 0) {
18            // If count1 is 0, replace candidate1 with the current element
19            candidate1 = num;
20            count1 = 1;
21        } else if (count2 === 0) {
22            // If count2 is 0, replace candidate2 with the current element
23            candidate2 = num;
24            count2 = 1;
25        } else {
26            // If the current element is not equal to either candidate and both counts are non-zero, decrement both counts
27            count1--;
28            count2--;
29        }
30    }
31
32    // Initialize a result array to store the final majority elements
33    const result: number[] = [];
34  
35    // Validate if the candidates are indeed majority elements
36    count1 = nums.filter(num => num === candidate1).length;
37    count2 = nums.filter(num => num === candidate2).length;
38  
39    // Add candidate1 to result if count is greater than a third of nums length
40    if (count1 > Math.floor(nums.length / 3)) {
41        result.push(candidate1);
42    }
43
44    // Add candidate2 to result if it's different from candidate1 and count is greater than a third of nums length
45    if (candidate1 !== candidate2 && count2 > Math.floor(nums.length / 3)) {
46        result.push(candidate2);
47    }
48
49    // Return the final result
50    return result;
51}
52

Time and Space Complexity

Time Complexity

The given code implements the Boyer-Moore Voting Algorithm variant to find all elements that appear more than \frac{N}{3} times in the list. The algorithm is separated into two major phases:

  1. Selection Phase: This phase runs through the list once (O(N) time), maintaining two potential majority elements along with their corresponding counters.

  2. Validation Phase: The phase ensures that the potential majority elements actually appear more than \frac{N}{3} times. It requires another traversal through the list for each of the two candidates to count the occurrences (O(N) time per candidate).

The total time complexity is O(N) for the selection phase plus 2 * O(N) for the validation phase, resulting in O(N).

Space Complexity

The space complexity is O(1), as the algorithm uses a constant amount of extra space to maintain the potential majority element candidates and their counters.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement priority queue?


Recommended Readings

Got a question?Β Ask the Monster AssistantΒ anything you don't understand.

Still not clear? Ask in the Forum, Β DiscordΒ orΒ SubmitΒ the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns
←
↑πŸͺ„