Online Majority Element In Subarray - Practice Coding Problems

Online Majority Element In Subarray - Problem

Design a data structure that efficiently finds the majority element of a given subarray. The majority element of a subarray is an element that occurs threshold times or more in the subarray.

Implement the MajorityChecker class:

MajorityChecker(int[] arr) - Initializes the instance of the class with the given array arr.
int query(int left, int right, int threshold) - Returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.

Input & Output

Example 1 — Basic Majority Check

$ Input: arr = [1,1,2,2,1,1], queries = [[0,5,4],[0,3,3],[2,3,2]]

› Output: [1,-1,2]

💡 Note: Query [0,5,4]: Element 1 appears 4 times in full array (≥4). Query [0,3,3]: No element appears ≥3 times in [1,1,2,2]. Query [2,3,2]: Element 2 appears 2 times in [2,2] (≥2).

Example 2 — No Majority Found

$ Input: arr = [1,2,3,4,5], queries = [[0,4,3]]

› Output: [-1]

💡 Note: In range [0,4], each element [1,2,3,4,5] appears only once, none meet threshold 3.

Example 3 — Small Range

$ Input: arr = [3,3,3], queries = [[0,2,2]]

› Output: [3]

💡 Note: Element 3 appears 3 times in range [0,2], which is ≥ threshold 2.

Constraints

1 ≤ arr.length ≤ 2 × 10⁴
1 ≤ arr[i] ≤ 2 × 10⁴
0 ≤ left ≤ right < arr.length
threshold ≤ right - left + 1
1 ≤ queries ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,1,2,2,1,1] and queries [[0,5,4]]

Process

Check if any element appears ≥ threshold times in range

Output

Return the majority element or -1

Key Takeaway

🎯 Key Insight: Random sampling makes majority detection extremely efficient since true majorities have high probability of being discovered quickly.

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is that true majority elements are rare, so random sampling can efficiently identify candidates. The optimal approach uses preprocessing with index maps plus randomized sampling for O(N + Q × S × log N) time complexity where S is small constant sample size.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Count Each Query	O(Q × N)	O(N)	For each query, iterate through the subarray and count frequency of each element
Random Sampling + Binary Search	O(N + Q × S × log N)	O(N)	Randomly sample elements from the query range, then verify potential majority candidates with binary search
Preprocessing with Index Maps	O(N + Q × K × log N)	O(N)	Preprocess array to store indices for each element, then use binary search for range counting

Brute Force - Count Each Query — Algorithm Steps

For each query, create empty frequency map
Iterate through subarray [left, right]
Count occurrences of each element
Find elements with count >= threshold

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Range

Select subarray [left, right]

Count Elements

Count frequency of each element

Check Threshold

Return element with count >= threshold

Code -

solution.c — C

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

#define MAX_N 20000
#define MAX_Q 10000

typedef struct {
    int arr[MAX_N];
    int size;
} MajorityChecker;

int query(MajorityChecker* mc, int left, int right, int threshold) {
    int count[100001] = {0};
    int minVal = 100001, maxVal = -100001;
    
    for (int i = left; i <= right; i++) {
        int val = mc->arr[i] + 50000; // Handle negative numbers
        count[val % 100001]++;
        if (mc->arr[i] < minVal) minVal = mc->arr[i];
        if (mc->arr[i] > maxVal) maxVal = mc->arr[i];
    }
    
    for (int i = left; i <= right; i++) {
        int val = mc->arr[i] + 50000;
        if (count[val % 100001] >= threshold) {
            return mc->arr[i];
        }
        count[val % 100001] = 0; // Mark as processed
    }
    
    return -1;
}

int* solution(int* arr, int arrSize, int queries[][3], int querySize, int* returnSize) {
    MajorityChecker mc;
    mc.size = arrSize;
    for (int i = 0; i < arrSize; i++) {
        mc.arr[i] = arr[i];
    }
    
    int* results = (int*)malloc(querySize * sizeof(int));
    for (int i = 0; i < querySize; i++) {
        results[i] = query(&mc, queries[i][0], queries[i][1], queries[i][2]);
    }
    
    *returnSize = querySize;
    return results;
}

int main() {
    // Simplified I/O for this example
    int arr[] = {1,1,2,2,1,1};
    int queries[][3] = {{0,5,4}, {0,3,3}, {2,3,2}};
    
    int returnSize;
    int* result = solution(arr, 6, queries, 3, &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(Q × N)

Q queries, each scanning up to N elements in worst case

✓ Linear Growth

Space Complexity

O(N)

Hash map stores up to N unique elements per query

✓ Linear Space

23.5K Views

Medium Frequency

~35 min Avg. Time

892 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 Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler