Majority Element - Practice Coding Problems

Majority Element - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,2,3]

› Output: 3

💡 Note: Element 3 appears 2 times, which is more than ⌊3/2⌋ = 1, so 3 is the majority element

Example 2 — Larger Array

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

› Output: 2

💡 Note: Element 2 appears 4 times, which is more than ⌊7/2⌋ = 3, so 2 is the majority element

Example 3 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: Only one element exists, so it's automatically the majority element

Constraints

n == nums.length
1 ≤ n ≤ 5 × 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with one element appearing > n/2 times

Count Frequencies

Count how many times each element appears

Find Majority

Return element with count > ⌊n/2⌋

Key Takeaway

🎯 Key Insight: The majority element appears more than half the time, so it will always survive when other elements cancel out

Asked in

🍎 Apple 15 G Google 12 a Amazon 10 M Microsoft 8

The key insight is that the majority element appears more than n/2 times, so it will always survive pairwise cancellation. Best approach is Boyer-Moore Voting Algorithm with optimal Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Boyer-Moore Voting Algorithm	O(n)	O(1)	Optimal O(1) space solution using voting algorithm
Hash Map Counting	O(n)	O(n)	Use hash map to count frequencies, then find majority
Brute Force	O(n²)	O(1)	Count occurrences of each element by nested loops
Sorting Approach	O(n log n)	O(1)	Sort array, majority element will be at middle position

Boyer-Moore Voting Algorithm — Algorithm Steps

Initialize candidate and count to 0
For each element: if count is 0, set as candidate; if same as candidate, increment count; else decrement count
Return the candidate as majority element

Visualization

Tap to expand

Step-by-Step Walkthrough

Vote Counting

Track candidate and vote count

Vote Changes

Increment for same, decrement for different

Result

Final candidate is majority element

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int candidate = 0;
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (count == 0) {
            candidate = nums[i];
        }
        count += (nums[i] == candidate) ? 1 : -1;
    }
    
    return candidate;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int nums[10000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the array

✓ Linear Growth

Space Complexity

O(1)

Only two variables: candidate and count

✓ Linear Space

411.5K Views

High Frequency

~15 min Avg. Time

15.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Boyer-Moore Voting Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler