169. Majority Element

EasyArrayHash TableDivide and ConquerCountingSorting

Problem Description

You are given an array called nums that has a certain number of elements, denoted as n. You have to find the majority element in this array. The majority element is defined as the one that appears more than n / 2 times. It's guaranteed that there is always a majority element in the array you're given.

Intuition

The intuition behind the solution comes from the understanding that if an element occurs more than n / 2 times, it means that element is present more often than all other elements combined. For every instance of a non-majority element, there must be more instances of the majority element. We can use this intuition with a clever algorithm known as the Moore Voting Algorithm.

The Moore Voting Algorithm works by keeping a current candidate for majority element and a counter. As it goes through the array, the algorithm either increases the count if the current number matches the candidate or decreases the count otherwise. When the count reaches zero, it means that up to that point, there is no majority element, and the algorithm selects the current number as the new candidate. The key insight is that the majority element's surplus count will withstand the count decrements due to non-majority elements.

Therefore, we initialize a counter cnt to zero and a majority element candidate m to none. Then, for each element x in nums, we make the following check:

If cnt is zero, we assume the current element x can be a new majority candidate m, and we set cnt to 1.
If cnt is not zero, we increase the count by 1 if x is equal to m (our current candidate), otherwise, we decrease the count.

After processing all elements of the array, our current candidate m is the majority element. Since we are guaranteed that a majority element exists, we don't need to verify m on a second pass.

Learn more about Divide and Conquer and Sorting patterns.

Solution Approach

The solution uses the Moore Voting Algorithm, which is efficient in finding the majority element of an array when such an element definitely exists.

The algorithm works in a single pass and uses constant extra space. It consists of two main variables: the candidate m representing the presumed majority element, and the counter cnt indicating the strength of our presumption that m is indeed the majority element.

To implement the algorithm, we iterate through each element x of the array nums. During this iteration, the following logic is applied:

When cnt equals zero, there's no current candidate for majority element, or the previous candidate has been completely offset by other elements. So we assign the current element x to be the new candidate m, and set cnt to 1, because we start counting the occurrences of m again.
If cnt is not zero, it means there's a candidate set and we need to compare the current element x with m.
- If x is equal to m, this means we've found another instance of our candidate, and we increment the counter cnt by 1, strengthening the candidacy of m.
- If x is not equal to m, this means we have encountered an element that opposes our candidate. To denote this opposition, we decrement the counter cnt by 1.

By the end of the loop, despite all the increments and decrements, the surplus repetitions of the majority element ensure that m will remain as the candidate and cnt will be greater than zero.

Given the guarantee that a majority element always exists, m is the majority element at the end of this single pass, and we can return m as the answer.

It's important to note that if the problem statement didn't guarantee the existence of a majority element, a second pass would be necessary to confirm that our candidate m is indeed the majority by counting its total occurrences in nums and comparing it to n / 2.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Assume we have an array nums = [3, 3, 1, 3, 2, 3]. We want to use the Moore Voting Algorithm to find the majority element. The majority element is the element that appears more than n / 2 times in the array (n is the size of the array which in this case is 6, so n / 2 is 3). The steps are as follows:

We initialize cnt to 0 and m to any value (let's choose m = None for the start).
Traverse the elements of nums:

Start with the first element (nums[0] = 3).
- Since cnt is 0, we set m = 3 and cnt = 1.
Move to the second element (nums[1] = 3).
- Since cnt is not 0 and m is equal to nums[1], we increment cnt to 2.
Proceed to the third element (nums[2] = 1).
- The current element is not equal to m, so we decrement cnt to 1.
Next, the fourth element (nums[3] = 3).
- The current element is equal to m, therefore cnt is incremented to 2.
Then, the fifth element (nums[4] = 2).
- This is not equal to m, and so cnt is decremented to 1.
Finally, the sixth element (nums[5] = 3).
- It is equal to m, meaning cnt gets incremented again, now cnt = 2.

Despite the increment and decrement of cnt, at the end of the traversal, m remains 3. Since cnt is greater than 0, we are left with m = 3 as the candidate for the majority element.
As the problem guarantees the presence of a majority element, we don't need to check m in a second pass. We declare that the majority element is 3.

By the end of the process, we successfully used the Moore Voting Algorithm to find the majority element which is 3 in the given example array.

Solution Implementation

1class Solution:
2    def majorityElement(self, nums: List[int]) -> int:
3        # Initialize the count and the candidate for majority element
4        count = 0
5        majority_candidate = None
6      
7        # Process each number in the list
8        for num in nums:
9            # If the current count is 0, we choose a new number as the potential majority candidate
10            if count == 0:
11                majority_candidate = num
12                count = 1
13            # If the current number is the same as the majority candidate, increase the count
14            elif majority_candidate == num:
15                count += 1
16            # Otherwise, decrease the count
17            else:
18                count -= 1
19      
20        # The majority candidate is the number that remains after pairing off different elements
21        return majority_candidate
22

1class Solution {
2  
3    // This method finds the majority element in an array, which is defined as the element that appears more than n/2 times
4    public int majorityElement(int[] nums) {
5        // Initialize count and candidate for majority element
6        int count = 0;
7        int candidate = 0;
8      
9        // Iterate over all elements in the array
10        for (int num : nums) {
11            // If count is zero, we choose the current element as the new candidate
12            if (count == 0) {
13                candidate = num;
14                count = 1;
15            } else {
16                // If the current element is the same as the candidate, increment count
17                if (num == candidate) {
18                    count++;
19                } else {
20                    // If different, decrement count
21                    count--;
22                }
23            }
24        }
25      
26        // The candidate is the majority element, which is guaranteed to exist
27        return candidate;
28    }
29}
30

1#include <vector> // Include the vector header for using the vector container
2
3class Solution {
4public:
5    // Function to find the majority element in the array
6    // A majority element is an element that appears more than n/2 times in the array
7    int majorityElement(vector<int>& nums) {
8        int count = 0; // Counter for the number of times the current candidate is found
9        int candidate = 0; // Variable to store the current potential majority element
10      
11        // Iterate through all the elements in the given array
12        for (int num : nums) {
13            if (count == 0) {
14                // If the count is 0, we select the current element as our new candidate for majority element
15                candidate = num;
16                count = 1; // Set the count for this new candidate to 1
17            } else {
18                // If count is not 0, increment or decrement the count
19                // Increment if the current element is the same as the candidate
20                // Decrement if it is different
21                count += (candidate == num) ? 1 : -1;
22            }
23        }
24      
25        // After the loop, the candidate is the majority element
26        // (due to the problem's guarantee that a majority element always exists)
27        return candidate;
28    }
29};
30

1function majorityElement(numbers: number[]): number {
2    // Initialize a count variable to keep track of the frequency of the majority element.
3    let count: number = 0;
4    // Initialize a variable to hold the current majority element.
5    let majorityElement: number = 0;
6  
7    // Iterate through each number in the numbers array.
8    for (const number of numbers) {
9        // If count is zero, we found a new possible majority element.
10        if (count === 0) {
11            majorityElement = number;
12            count = 1;
13        }
14        // If the current number is the same as the majority element, increment the count.
15        // Otherwise, decrement the count.
16        else {
17            count += (majorityElement === number) ? 1 : -1;
18        }
19    }
20  
21    // At the end of the loop, the majorityElement variable will contain the majority element.
22    return majorityElement;
23}
24

Time and Space Complexity

The given Python code snippet is an implementation of the Boyer-Moore Voting Algorithm, designed to find a majority element (an element that appears more than n/2 times) from a list. The time complexity and space complexity of this algorithm are analyzed as follows:

Time Complexity:

The function iterates through the list nums exactly once. For each element x in nums, the code executes a constant number of operations, either incrementing, decrementing, or setting the count cnt and possibly updating the candidate majority element m. Thus, the number of operations is proportional to the length of nums, which is n. Therefore, the time complexity is O(n).

Space Complexity:

The algorithm uses a fixed amount of extra space: two variables cnt and m to keep track of the current count and the potential majority element respectively. The amount of space used does not depend on the size of the input list, therefore, the space complexity is constant, O(1).

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:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know