Majority Element (>n/2 times)

Problem Overview

The LeetCode question "Majority Element" (URL: LeetCode Majority Element) involves identifying the majority element in an array. This problem is categorized under Arrays. Given an array of size n, the task is to find the element that appears more than n/2 times. It is guaranteed that such an element always exists in the array.

Understanding the Problem

To solve this problem, an efficient algorithm must be implemented to find the majority element, which appears more than half of the time in the array. The challenge here is to achieve this in a time-efficient manner (preferably linear time) without using excessive space.

Example:

• Input: [3, 2, 3]
• Output: 3

In this example, the majority element is 3 since it appears twice, which is more than 3/2 times.

Key DSA Concepts and Theory

Array

An array is a collection of items stored at contiguous memory locations. Arrays are used to store multiple items of the same data type efficiently. The problem involves iterating through an array to find a majority item.

Boyer-Moore Voting Algorithm

The Boyer-Moore Voting Algorithm is a clever voting algorithm used to find the majority element in linear time and constant space. The algorithm works as follows:

1. Initialize candidate to any element in the array and count to zero.
2. Traverse the array, and for each element x:
   • If count is zero, assign x as the new candidate.
   • If x is the current candidate, increment count. Otherwise, decrement count.
3. After completion, candidate will be the majority element.

The algorithm takes advantage of the properties of the majority element, ensuring that its count remains positive while iterating through the array.

Solution Approach

Here we will describe a step-by-step approach to solving this problem, using the Boyer-Moore Voting Algorithm. We provide implementations in both C++ and Java.

Step 1: Initialize variables

Create a candidate variable and a count variable. Start candidate with any arbitrary value from the array and count as 0.

Step 2: Traverse the Array

Iterate through each element of the array and apply the vote counting mechanism described in the algorithm.

Step 3: Return the Candidate

After completion of the iteration, return the candidate, which will be the majority element.

C++ Code

#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
};

Java Code

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

Time and Space Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the array. This efficiency is achieved by iterating through the array only once.

Space Complexity

The space complexity is O(1) as the Boyer-Moore Voting Algorithm uses only a constant amount of extra space.

Common Mistakes to Avoid

1. Assuming no majority: The problem specifies that a majority element always exists, so there's no need to handle input without a majority.
2. Incorrect counting logic: Ensure that the count is correctly incremented and decremented based on the comparison between candidate and current element.

Similar Problems on LeetCode

• Problem #229: Majority Element II
• Problem #169: Majority Element
• Problem #136: Single Number

Additional Resources and References

• Wikipedia: Boyer-Moore Majority Vote Algorithm
• LeetCode Discuss: Explanation of the Boyer-Moore Voting Algorithm

The "Majority Element" problem strengthens your understanding of arrays and offers insights into efficient algorithms that leverage mathematical properties like the Boyer-Moore Voting Algorithm. With practice, the concepts here are applicable to a wide range of array-based problems.