Problem Explanation

We are given an array of size n and we need to find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times in the array. We can assume that the array is never empty and the majority element always exists in the array.

The problem can be solved by using the Boyer-Moore Voting Algorithm. The basic idea of the Boyer-Moore Voting Algorithm is that in each round of voting, we maintain a candidate, that could potentially be the majority element. We vote (add count) for each occurrence of this candidate and vote against (subtract count) for every other element.

Through rounds of voting, the majority would gain more votes and the minority would lose votes until the majority’s votes win out. This happens because the majority element appears more than ⌊ n/2 ⌋ times, thus it is guaranteed to result in positive votes at the end.

Solution Approach

1. Initialize a variable count to 0 and a variable candidate to some value.

2. For each number num in our given array, if count is 0, set num as the candidate.

3. If num equals candidate, increment count by 1. If num doesn't equal candidate, decrement count by 1.

4. Once all numbers have been assessed, candidate will be the majority element.

Solution Walkthrough

• Take an example {3,2,3}. We initialize count as 0 and candidate as None.

• For the first element 3, count is 0, so we make 3 as candidate and increment count to 1.

• The next number is 2, which is not equal to candidate, so we decrement count to 0.

• The last number is 3, count is 0, so we make 3 as candidate and increment count to 1.

• Now, all numbers have been assessed and our candidate is 3 which is indeed the majority element.

Python Solution

1
2python
3class Solution:
4  def majorityElement(self, nums: List[int]) -> int:
5    count = 0
6    candidate = None
7
8    for num in nums:
9      if count == 0:
10        candidate = num
11      count += (1 if num == candidate else -1)
12    
13    return candidate

Java Solution

1
2java
3public class Solution{
4  public int majorityElement(int[] nums) {
5    int count = 0;
6    Integer candidate = null;
7
8    for (int num: nums){
9      if (count == 0){
10        candidate = num;
11      }
12      count += (num == candidate) ? 1: -1;
13    }
14
15    return candidate;
16  }
17}

JavaScript Solution

1
2javascript
3class Solution {
4  majorityElement(nums) {
5    let count = 0;
6    let candidate = null;
7
8    for (let num of nums) {
9      if (count == 0) {
10        candidate = num;
11      }
12      count += (num == candidate) ? 1 : -1;
13    }
14
15    return candidate;
16  }
17}

C++ Solution

1
2c++
3class Solution {
4public:
5  int majorityElement(vector<int>& nums) {
6    int count = 0;
7    int candidate;
8
9    for (int num: nums) {
10      if (count == 0){
11        candidate = num;
12      }
13      if (num == candidate){
14        count++;
15      }
16      else {
17        count--;
18      }
19    }
20
21    return candidate;
22  }
23};

C# Solution

1
2csharp
3public class Solution {
4    public int MajorityElement(int[] nums) {
5        int count = 0;
6        int? candidate = null;
7
8        foreach (int num in nums) {
9            if (count == 0){
10                candidate = num;
11            }
12            count += (num == candidate) ? 1 : -1;
13        }
14
15        return candidate.Value;
16    }
17}

Note

In the given solutions, we use the ternary operator to increment or decrement the count based on whether the current number is the candidate or not. If the current number is the candidate, we increment the count, else we decrement the count.The final majority element is the one that remains after all pairs of non-equal elements are removed. The count of candidate if it's a majority element will always be positive at the end. Therefore, by maintaining a count that increments when we encounter the candidate and decrements when we encounter other elements, we ensure that the majority's votes win.

Time Complexity

This algorithm works in O(n) time where n is the total number of elements in the array. This is because we are iterating over the array just once. For each element, we are performing a constant amount of work (updating the count and possibly setting the candidate). Therefore, the overall time complexity is O(n).

Space Complexity

The space complexity of the algorithm is O(1), that is, constant space complexity. We have used only a constant amount of space to store the candidate and the count. Regardless of the size of the input, the amount of space used does not increase.

Conclusion

The problem of finding the majority element in an array can be solved efficiently using the Boyer-Moore Voting Algorithm. Our solutions in Python, JavaScript, and Java implement this algorithm and successfully find the majority element with O(n) time complexity and O(1) space complexity, making it a practical solution for large inputs.