LeetCode problem#169

Majority Element

Solved in 2 languagesCC#

25 lines

1// Boyer–Moore majority vote algorithm
2// time O(n), space O(1)
3int majorityElement(int* nums, int numsSize) {
4    int count = 0;
5    int majority = 0;
6
7    for (int i = 0; i < numsSize; i++)
8    {
9        if (count == 0)
10        {
11            majority = nums[i];
12            count = 1;
13        }
14        else if (nums[i] == majority)
15        {
16            count++;
17        }
18        else
19        {
20            count--;
21        }
22    }
23
24    return majority;
25}

1public class Solution {
2    // Boyer–Moore majority vote algorithm
3    // time O(n), space O(1)
4    public int MajorityElement(int[] nums) {
5        int count = 0;
6        int majority = 0;
7
8        for (int i = 1; i < nums.Length; i++)
9        {
10            if (count == 0) {
11                majority = nums[i];
12                count = 1;
13            }
14            else if (nums[i] == majority)
15            {
16                count++;
17            }
18            else
19            {
20                count--;
21            }
22        }
23
24        return majority;
25    }
26}

How it works

The provided solution implements the Boyer–Moore majority vote algorithm, which is a classic algorithm used to efficiently find the majority element in an array. The majority element is defined as the element that appears more than half of the time in the array.

Explanation of the Code:

Initialization:
- count is initialized to 0, which will be used to track the "strength" of a potential majority candidate.
- majority is initialized to 0 (it could be any value), which will eventually store the majority element.
Iterating through the Array:
- The algorithm loops through each element of the array nums using the index i:
Finding the Potential Majority Element:
- When count is 0:
  - It means that there is currently no candidate for the majority element, or the current candidate has lost its support.
  - In this case, the algorithm sets majority to the current element nums[i] and resets count to 1, indicating that we are starting to count votes for this new candidate.
- If count is not 0:
  - The algorithm checks if the current element nums[i] is the same as the current majority candidate.
    - If it is the same, it increments count because the candidate has received one more vote.
    - If it is not the same, it decrements count because the current candidate has lost a vote.
Final Result:
- After iterating through the entire array, the variable majority holds the candidate that is the majority element, which is returned.

Why This Works:

The key idea behind the algorithm is that the count variable represents the net votes for the majority candidate.
If at any point the majority candidate is outvoted, the count decrements. If a candidate is not a majority, the net effect of equal upvotes and downvotes will never allow any non-majority candidate to remain when the counter reaches 0.
Since a majority element is guaranteed to exist (as per the problem statement), at the end of the iteration, majority will indeed contain the correct majority element.

Time and Space Complexity:

Time Complexity: O(n) - The algorithm makes a single pass through the array of size n, performing a constant amount of work for each element.
Space Complexity: O(1) - The algorithm only uses a fixed amount of extra space (the integer variables count and majority), regardless of the input size.

Conclusion:

This algorithm is both efficient and elegant for finding a majority element in an array because it maintains a simple counting mechanism that adapts to the data it processes.

Written by AI from the code above, so double-check anything important.

All problems

Problem statements belong to LeetCode and are on leetcode.com. We're not affiliated with LeetCode.