Majority Element

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n/2⌋ times. You may assume that the majority element always exists in the array.

Examples:

Input: nums = [3,2,3]

Output: 3

Input: nums = [2,2,1,1,2,2]

Output: 2

Input: nums = [1,1,1,2,2,2,2]

Output: 2

Constraints

n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹

Editorial

Intuition:

Since the majority element appears more than ⌊n/2⌋ times, we can use the Boyer-Moore Voting Algorithm. It works by maintaining a candidate and a count. Each element either supports the current candidate (increment count) or opposes it (decrement count). When the count drops to zero, we pick a new candidate. The final candidate is guaranteed to be the majority element.

Approach:

Initialize candidate as None and count as 0.
Iterate through each number in the array:

If count is 0, set candidate to the current number.
If the current number equals candidate, increment count.
Otherwise, decrement count.

After processing all numbers, candidate holds the majority element.

#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(const vector<int>& nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
};
class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}
class Solution:
    def majority_element(self, nums):
        candidate = None
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate
class Solution {
    majorityElement(nums) {
        let candidate = null;
        let count = 0;
        for (const num of nums) {
            if (count === 0) {
                candidate = num;
            }
            count += (num === candidate) ? 1 : -1;
        }
        return candidate;
    }
}

Complexity Analysis:

Time Complexity: O(n), where n is the length of the array. We traverse the array once.

Space Complexity: O(1), we only use two extra variables (candidate and count).

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories