Majority Element II - Practice Coding Problems

Majority Element II - Problem

Given an integer array nums of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

The algorithm should run in linear time and use only constant extra space.

Note: There can be at most two elements that appear more than ⌊ n/3 ⌋ times in any array.

Input & Output

Example 1 — Basic Case

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

› Output: [3]

💡 Note: Element 3 appears 2 times out of 3 total. Since 2 > ⌊3/3⌋ = 1, element 3 is a majority element.

Example 2 — No Majority

$ Input: nums = [1]

› Output: [1]

💡 Note: Element 1 appears 1 time out of 1 total. Since 1 > ⌊1/3⌋ = 0, element 1 is a majority element.

Example 3 — Two Majority Elements

$ Input: nums = [1,2]

› Output: [1,2]

💡 Note: Both elements appear 1 time out of 2 total. Since 1 > ⌊2/3⌋ = 0, both are majority elements.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with n=3, threshold = n/3 = 1

Count Elements

Find frequency of each unique element

Filter Result

Return elements with count > threshold

Key Takeaway

🎯 Key Insight: At most 2 elements can appear more than n/3 times, enabling Boyer-Moore optimization

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is that at most 2 elements can appear more than n/3 times in any array. The optimal approach uses the Boyer-Moore Majority Vote algorithm modified for 2 candidates, achieving O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Count Each Element	O(n²)	O(n)	For each unique element, count its occurrences across the entire array
Hash Map - Two Pass Count	O(n)	O(n)	Use hash map to count frequencies, then filter elements with count > n/3
Boyer-Moore Majority Vote - Optimal	O(n)	O(1)	Use Boyer-Moore algorithm to find at most 2 candidates, then verify their counts

Brute Force - Count Each Element — Algorithm Steps

Step 1: Get unique elements from array
Step 2: For each unique element, count occurrences
Step 3: Add elements with count > n/3 to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Unique Elements

Identify all unique values in array

Count Occurrences

For each unique element, scan entire array to count

Filter Results

Keep elements with count > n/3

Code -

solution.c — C

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

int* solution(int* nums, int numsSize, int* returnSize) {
    int threshold = numsSize / 3;
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 0;
    bool* seen = (bool*)calloc(20001, sizeof(bool));
    
    for (int i = 0; i < numsSize; i++) {
        int idx = nums[i] + 10000;
        if (!seen[idx]) {
            seen[idx] = true;
            int count = 0;
            for (int j = 0; j < numsSize; j++) {
                if (nums[j] == nums[i]) count++;
            }
            if (count > threshold) {
                result[(*returnSize)++] = nums[i];
            }
        }
    }
    
    free(seen);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n elements, we scan the entire array of n elements

⚠ Quadratic Growth

Space Complexity

O(n)

Result array can store up to 2 elements, plus temporary storage for unique elements

⚡ Linearithmic Space

78.9K Views

Medium Frequency

~25 min Avg. Time

2.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

Brute Force - Count Each Element — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler