229. Majority Element II

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.

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

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.