Online Majority Element In Subarray

hard design binary search random pick

Problem

Design a data structure built from a fixed array arr that answers queries of the form query(left, right, threshold): return the element that appears at least threshold times in the subarray arr[left..right], or -1 if no such element exists. The threshold is always strictly more than half the subarray length, so the answer (if any) is unique. During preprocessing we group each value's indices into a sorted position list; per query we pick a few random candidates and verify each by counting its occurrences inside [left, right] with two binary searches.

Inputarr = [1, 1, 2, 2, 1, 1], query(0, 5, 4)

Output1

Value 1 sits at indices [0, 1, 4, 5]; all four are inside [0, 5], so its count is 4 ≥ threshold 4. Return 1.

arr (comma-separated)

left

right

threshold

import bisect, random

class MajorityChecker:
    def __init__(self, arr):
        self.arr = arr
        self.pos = {}
        for i, x in enumerate(arr):
            self.pos.setdefault(x, []).append(i)

    def query(self, left, right, threshold):
        for _ in range(20):
            x = self.arr[random.randint(left, right)]
            idx = self.pos[x]
            lo = bisect.bisect_left(idx, left)
            hi = bisect.bisect_right(idx, right)
            if hi - lo >= threshold:
                return x
        return -1

class MajorityChecker {
  constructor(arr) {
    this.arr = arr;
    this.pos = new Map();
    arr.forEach((x, i) => {
      if (!this.pos.has(x)) this.pos.set(x, []);
      this.pos.get(x).push(i);
    });
  }
  lowerBound(a, t) {
    let lo = 0, hi = a.length;
    while (lo < hi) { const m = (lo + hi) >> 1; a[m] < t ? lo = m + 1 : hi = m; }
    return lo;
  }
  query(left, right, threshold) {
    for (let t = 0; t < 20; t++) {
      const x = this.arr[left + ((Math.random() * (right - left + 1)) | 0)];
      const idx = this.pos.get(x);
      const lo = this.lowerBound(idx, left);
      const hi = this.lowerBound(idx, right + 1);
      if (hi - lo >= threshold) return x;
    }
    return -1;
  }
}

class MajorityChecker {
    int[] arr;
    Map<Integer, List<Integer>> pos = new HashMap<>();
    Random rng = new Random();

    public MajorityChecker(int[] arr) {
        this.arr = arr;
        for (int i = 0; i < arr.length; i++)
            pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
    }

    int lowerBound(List<Integer> a, int t) {
        int lo = 0, hi = a.size();
        while (lo < hi) { int m = (lo + hi) >>> 1; if (a.get(m) < t) lo = m + 1; else hi = m; }
        return lo;
    }

    public int query(int left, int right, int threshold) {
        for (int t = 0; t < 20; t++) {
            int x = arr[left + rng.nextInt(right - left + 1)];
            List<Integer> idx = pos.get(x);
            int lo = lowerBound(idx, left), hi = lowerBound(idx, right + 1);
            if (hi - lo >= threshold) return x;
        }
        return -1;
    }
}

class MajorityChecker {
    vector<int> arr;
    unordered_map<int, vector<int>> pos;
public:
    MajorityChecker(vector<int>& a) : arr(a) {
        for (int i = 0; i < (int)a.size(); i++) pos[a[i]].push_back(i);
    }
    int query(int left, int right, int threshold) {
        for (int t = 0; t < 20; t++) {
            int x = arr[left + rand() % (right - left + 1)];
            auto& idx = pos[x];
            int lo = lower_bound(idx.begin(), idx.end(), left) - idx.begin();
            int hi = upper_bound(idx.begin(), idx.end(), right) - idx.begin();
            if (hi - lo >= threshold) return x;
        }
        return -1;
    }
};

Explanation

The neat trick here leans on a guarantee in the problem: the threshold is always more than half the subarray length. That means the answer, if it exists, is a true majority — so a randomly chosen element from the window has a better-than-even chance of being it. Try a few random picks and you will almost certainly hit it.

During setup we build pos, a map from each value to the sorted list of indices where it appears. This costs one pass over arr.

For a query we repeat up to 20 times: grab a random element x from inside [left, right], then count how many times it actually falls in that window. Because pos[x] is sorted, two binary searches give the count instantly: lo is the first index >= left and hi is the first index > right, so hi - lo is the occurrence count. If that reaches the threshold, return x; otherwise try another candidate.

Example: arr = [1,1,2,2,1,1], query(0,5,4). Value 1 lives at indices [0,1,4,5]. All four are within [0,5], so hi - lo = 4 >= 4 and we return 1.

Setup is O(n), and each query is a constant number of binary searches, so O(log n) per query.

Time: O(n) build, O(log n) per query Space: O(n)