1157. Online Majority Element In Subarray Solution

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

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

Example 1:

Input
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
Output
[null, 1, -1, 2]

Explanation
MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);
majorityChecker.query(0, 5, 4); // return 1
majorityChecker.query(0, 3, 3); // return -1
majorityChecker.query(2, 3, 2); // return 2

Constraints:

1 <= arr.length <= 2 * 10⁴
1 <= arr[i] <= 2 * 10⁴
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
At most 10⁴ calls will be made to query.

Approach overview

Problem Overview: You receive an integer array and many queries of the form (left, right, threshold). For each query, return the element that appears at least threshold times inside the subarray arr[left...right]. If no such element exists, return -1. Since queries are online and frequent, repeatedly scanning the subarray is too slow.

Approach 1: Hash Map with Preprocessing + Binary Search (Average O(log n) per query, O(n) space)

Preprocess the array using a hash map that stores a sorted list of indices for every distinct value. This allows you to count how many times a value appears inside any range using binary search. During a query, randomly sample a few indices from the range [left, right]. Each sampled value becomes a candidate majority. Use binary search on its index list to count occurrences inside the range and check whether it meets the threshold. Each verification takes O(log n), and sampling a small constant number of candidates keeps the expected query time close to O(log n). This approach relies on the probability that a true majority element will be sampled quickly.

The key idea is fast frequency verification. The hash map stores value → sorted indices, and binary search finds the first and last positions inside the query range. You avoid scanning the entire subarray while still confirming exact counts. This technique combines array preprocessing with binary search for efficient range counting.

Approach 2: Segment Tree with Majority Candidate (O(log n) query, O(n) space)

A more deterministic solution builds a segment tree. Each node stores a candidate element and a relative count using the Boyer–Moore majority merge idea. When combining two segments, if both candidates match, their counts add; otherwise the larger count survives after subtraction. This process propagates a potential majority candidate upward.

For a query range, the segment tree returns a candidate in O(log n). That candidate may not actually meet the threshold, so verify it using the same preprocessing map of value → sorted indices. Counting occurrences with binary search takes O(log n). The overall query cost becomes O(log n) with reliable worst‑case behavior.

This design separates two responsibilities: the segment tree quickly proposes a candidate, while the index map verifies its true frequency. The tree handles range queries efficiently, and binary search provides exact counts without scanning the array.

Recommended for interviews: Start by explaining why brute force O(n) per query is too slow when queries are large. Then move to the segment tree approach. Interviewers typically expect a range-query structure combined with frequency verification. The hash map preprocessing shows good practical optimization, while the segment tree demonstrates strong understanding of range data structures.

Approach 1: Hash Map with Preprocessing

Preprocess the input array to create a map that keeps count of the index positions for each element. Use this map to efficiently determine the count of an element in any given subarray, enabling quick queries for the majority element.

Python

from collections import defaultdict

class MajorityChecker:
    def __init__(self, arr):
        self.arr = arr
        self.indices_map = defaultdict(list)
        for index, num in enumerate(arr):
            self.indices_map[num].append(index)

    def query(self, left, right, threshold):
        for num in set(self.arr[left:right+1]):
            indices = self.indices_map[num]
            low = self.binary_search(indices, left, True)
            high = self.binary_search(indices, right, False)
            if high - low + 1 >= threshold:
                return num
        return -1

    def binary_search(self, arr, target, find_first):
        start, end = 0, len(arr) - 1
        result = -1
        while start <= end:
            mid = (start + end) // 2
            if arr[mid] < target:
                start = mid + 1
            elif arr[mid] > target:
                end = mid - 1
            else:
                result = mid
                if find_first:
                    end = mid - 1
                else:
                    start = mid + 1
        return start if find_first else end

JavaScript

class MajorityChecker {
  constructor(arr) {
    this.arr = arr;
    this.posMap = {};
    arr.forEach((num, idx) => {
      if (!this.posMap[num]) this.posMap[num] = [];
      this.posMap[num].push(idx);
    });
  }

  binarySearch(array, target, isFirst) {
    let low = 0, high = array.length - 1, result = -1;
    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (array[mid] < target) low = mid + 1;
      else if (array[mid] > target) high = mid - 1;
      else {
        result = mid;
        if (isFirst) high = mid - 1;
        else low = mid + 1;
      }
    }
    return low if isFirst else high;
  }

  query(left, right, threshold) {
    const subarray = this.arr.slice(left, right + 1);
    const uniqueNums = new Set(subarray);
    for (let num of uniqueNums) {
      const indices = this.posMap[num];
      const low = this.binarySearch(indices, left, true);
      const high = this.binarySearch(indices, right, false);
      if (high - low + 1 >= threshold) return num;
    }
    return -1;
  }
}

This solution uses a defaultdict to store the indices of each element in the array. When a query is made, it checks possible candidates based on the existing numbers in the subarray, and verifies their frequency using binary search to locate their positions quickly.

Complexity

Time Complexity: O(n log n) for preprocessing and O(k log m) for each query, where k is the number of unique elements in the subarray and m is their frequency. Space Complexity: O(n), where n is the length of the array due to storage of indices.

Try this approach in the editor

Approach 2: Segment Tree with Lazy Propagation

Use a segment tree to preprocess the given array. Each node in the segment tree maintains information about the majority element in that segment along with its frequency. Lazy propagation is used to efficiently update ranges during queries.

Java

import java.util.HashMap;
import java.util.Map;

class MajorityChecker {
    private int[] nums;
    private Map<Integer, int[]> segTree;

    public MajorityChecker(int[] arr) {
        nums = arr;
        segTree = new HashMap<>();
        build(1, 0, nums.length - 1);
    }

    private int[] build(int node, int start, int end) {
        if (start == end) {
            return segTree.put(node, new int[]{nums[start], 1});
        }
        int mid = start + (end - start) / 2;
        int[] left = build(2 * node, start, mid);
        int[] right = build(2 * node + 1, mid + 1, end);
        return segTree.put(node, merge(left, right));
    }

    private int[] merge(int[] left, int[] right) {
        if (left[0] == right[0]) {
            return new int[]{left[0], left[1] + right[1]};
        } else if (left[1] > right[1]) {
            return new int[]{left[0], left[1] - right[1]};
        } else {
            return new int[]{right[0], right[1] - left[1]};
        }
    }

    public int query(int left, int right, int threshold) {
        int[] res = query(1, 0, nums.length - 1, left, right);
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (nums[i] == res[0]) count++;
        }
        return count >= threshold ? res[0] : -1;
    }

    private int[] query(int node, int start, int end, int L, int R) {
        if (R < start || end < L) return new int[]{0, 0};
        if (L <= start && end <= R) return segTree.get(node);
        int mid = start + (end - start) / 2;
        int[] left = query(node * 2, start, mid, L, R);
        int[] right = query(node * 2 + 1, mid + 1, end, L, R);
        return merge(left, right);
    }
}

C++

#include <vector>
#include <unordered_map>
using namespace std;

class MajorityChecker {
    vector<pair<int, int>> segTree;
    vector<int> nums;

    pair<int, int> merge(pair<int, int> left, pair<int, int> right) {
        if (left.first == right.first) {
            return {left.first, left.second + right.second};
        } else if (left.second > right.second) {
            return {left.first, left.second - right.second};
        } else {
            return {right.first, right.second - left.second};
        }
    }

    void build(int node, int start, int end) {
        if (start == end) {
            segTree[node] = {nums[start], 1};
        } else {
            int mid = (start + end) / 2;
            build(node*2, start, mid);
            build(node*2+1, mid+1, end);
            segTree[node] = merge(segTree[node*2], segTree[node*2+1]);
        }
    }

    pair<int, int> query(int node, int start, int end, int L, int R) {
        if (R < start || end < L) return {0, 0};
        if (L <= start && end <= R) return segTree[node];
        int mid = (start + end) / 2;
        auto left = query(node*2, start, mid, L, R);
        auto right = query(node*2+1, mid+1, end, L, R);
        return merge(left, right);
    }

public:
    MajorityChecker(vector<int>& arr): nums(arr) {
        segTree.resize(arr.size() * 4);
        build(1, 0, nums.size() - 1);
    }

    int query(int left, int right, int threshold) {
        auto res = query(1, 0, nums.size() - 1, left, right);
        int count = 0;
        for (int i = left; i <= right; ++i) {
            if (nums[i] == res.first) ++count;
        }
        return count >= threshold ? res.first : -1;
    }
};

This Java implementation uses a similar segment tree approach to efficiently handle range threshold queries by processing and merging segments, maintaining a map of segment nodes where each node holds the potential majority element and its frequency.

Complexity

Time Complexity: O(n) for build, O(log n + k) per query, where k is actual merges that occur in the operation. Space Complexity: O(n) for segment tree storage.

Try this approach in the editor

Approach 3: Segment Tree + Boyer-Moore Voting Algorithm + Binary Search

We notice that the problem requires us to find the possible majority element in a specific interval, so we consider using a segment tree to maintain the candidate majority element and its occurrence in each interval.

We define each node of the segment tree as Node, each node contains the following attributes:

l: The left endpoint of the node, the index starts from 1.
r: The right endpoint of the node, the index starts from 1.
x: The candidate majority element of the node.
cnt: The occurrence of the candidate majority element of the node.

The segment tree mainly has the following operations:

build(u, l, r): Build the segment tree.
pushup(u): Use the information of the child nodes to update the information of the parent node.
query(u, l, r): Query the interval sum.

In the initialization method of the main function, we first create a segment tree, and use a hash table d to record all indexes of each element in the array.

In the query(left, right, threshold) method, we directly call the query method of the segment tree to get the candidate majority element x. Then use binary search to find the first index l in the array that is greater than or equal to left, and the first index r that is greater than right. If r - l \ge threshold, return x, otherwise return -1.

In terms of time complexity, the time complexity of the initialization method is O(n), and the time complexity of the query method is O(log n). The space complexity is O(n). Here, n is the length of the array.

type node struct {
	l, r, x, cnt int
}

type segmentTree struct {
	nums []int
	tr   []*node
}

type pair struct{ x, cnt int }

func newSegmentTree(nums []int) *segmentTree {
	n := len(nums)
	tr := make([]*node, n<<2)
	for i := range tr {
		tr[i] = &node{}
	}
	t := &segmentTree{nums, tr}
	t.build(1, 1, n)
	return t
}

func (t *segmentTree) build(u, l, r int) {
	t.tr[u].l, t.tr[u].r = l, r
	if l == r {
		t.tr[u].x = t.nums[l-1]
		t.tr[u].cnt = 1
		return
	}
	mid := (l + r) >> 1
	t.build(u<<1, l, mid)
	t.build(u<<1|1, mid+1, r)
	t.pushup(u)
}

func (t *segmentTree) query(u, l, r int) pair {
	if t.tr[u].l >= l && t.tr[u].r <= r {
		return pair{t.tr[u].x, t.tr[u].cnt}
	}
	mid := (t.tr[u].l + t.tr[u].r) >> 1
	if r <= mid {
		return t.query(u<<1, l, r)
	}
	if l > mid {
		return t.query(u<<1|1, l, r)
	}
	left, right := t.query(u<<1, l, r), t.query(u<<1|1, l, r)
	if left.x == right.x {
		left.cnt += right.cnt
	} else if left.cnt >= right.cnt {
		left.cnt -= right.cnt
	} else {
		right.cnt -= left.cnt
		left = right
	}
	return left
}

func (t *segmentTree) pushup(u int) {
	if t.tr[u<<1].x == t.tr[u<<1|1].x {
		t.tr[u].x = t.tr[u<<1].x
		t.tr[u].cnt = t.tr[u<<1].cnt + t.tr[u<<1|1].cnt
	} else if t.tr[u<<1].cnt >= t.tr[u<<1|1].cnt {
		t.tr[u].x = t.tr[u<<1].x
		t.tr[u].cnt = t.tr[u<<1].cnt - t.tr[u<<1|1].cnt
	} else {
		t.tr[u].x = t.tr[u<<1|1].x
		t.tr[u].cnt = t.tr[u<<1|1].cnt - t.tr[u<<1].cnt
	}
}

type MajorityChecker struct {
	tree *segmentTree
	d    map[int][]int
}

func Constructor(arr []int) MajorityChecker {
	tree := newSegmentTree(arr)
	d := map[int][]int{}
	for i, x := range arr {
		d[x] = append(d[x], i)
	}
	return MajorityChecker{tree, d}
}

func (this *MajorityChecker) Query(left int, right int, threshold int) int {
	x := this.tree.query(1, left+1, right+1).x
	l := sort.SearchInts(this.d[x], left)
	r := sort.SearchInts(this.d[x], right+1)
	if r-l >= threshold {
		return x
	}
	return -1
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * obj := Constructor(arr);
 * param_1 := obj.Query(left,right,threshold);
 */

Try this approach in the editor

Complexity comparison

Approach	Complexity
Hash Map with Preprocessing	Time Complexity: O(n log n) for preprocessing and O(k log m) for each query, where k is the number of unique elements in the subarray and m is their frequency. Space Complexity: O(n), where n is the length of the array due to storage of indices.
Segment Tree with Lazy Propagation	Time Complexity: O(n) for build, O(log n + k) per query, where k is actual merges that occur in the operation. Space Complexity: O(n) for segment tree storage.
Segment Tree + Boyer-Moore Voting Algorithm + Binary Search	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Frequency Count	O(n) per query	O(1)	Small arrays or very few queries
Hash Map + Random Sampling + Binary Search	Expected O(log n) per query	O(n)	Practical solution with fast average performance
Segment Tree with Majority Candidate	O(log n) query, O(n) build	O(n)	Deterministic approach for many range queries

Frequently asked questions

Is Online Majority Element In Subarray easy or hard?

Online Majority Element In Subarray is classified as a Hard problem on LeetCode. The difficulty comes from handling many online queries efficiently and combining multiple techniques such as preprocessing, segment trees, and binary search verification.

Online Majority Element In Subarray Python/Java solution

Python implementations often use a dictionary mapping values to sorted index lists plus random sampling and binary search for verification. Java and C++ solutions frequently combine the same index map with a segment tree that returns a majority candidate for each query.

How to solve Online Majority Element In Subarray in O(log n)?

Build a segment tree where each node stores a potential majority candidate using a Boyer–Moore style merge. For a query range, retrieve the candidate in O(log n). Then count its occurrences in the range using binary search on a preprocessed list of indices to verify whether it meets the threshold.

What is the best approach for Online Majority Element In Subarray?

The most reliable approach uses a segment tree to produce a potential majority candidate for a range and then verifies the candidate using a preprocessed index map with binary search. Each query runs in O(log n) time after O(n) preprocessing. This balances fast queries with guaranteed correctness.

Is Online Majority Element In Subarray asked at Google/Amazon/Meta?

Range query problems involving segment trees, frequency counting, and majority voting patterns appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. This problem tests both data structure design and query optimization.

What data structure is used in Online Majority Element In Subarray?

Common data structures include hash maps for preprocessing value positions, binary search for fast range counting, and segment trees for efficient range candidate queries. These structures allow queries to run in logarithmic time instead of scanning subarrays.

What is the time complexity of Online Majority Element In Subarray?

Efficient solutions answer each query in O(log n) time. Preprocessing the array and building supporting data structures such as an index map or segment tree takes O(n). Verification of a candidate majority typically uses binary search on stored indices.

Online Majority Element In Subarray solution and explanation

The problem

Approach overview

Approach 1: Hash Map with Preprocessing

Approach 2: Segment Tree with Lazy Propagation

Approach 3: Segment Tree + Boyer-Moore Voting Algorithm + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Online Majority Element In Subarray solution and explanation

The problem

Approach overview

Approach 1: Hash Map with Preprocessing

Approach 2: Segment Tree with Lazy Propagation

Approach 3: Segment Tree + Boyer-Moore Voting Algorithm + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems