Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1262. Online Majority Element In Subarray

My accepted Python solution to LeetCode problem 1262, Online Majority Element In Subarray, running in 534ms.

  • Difficulty: Hard
  • Python
  • Runtime 534ms
  • Memory 28MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 534ms, memory 28MB, accepted 2026-01-02.

python
import random
from collections import defaultdict
import bisect

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.positions = defaultdict(list)
        for i, num in enumerate(arr):
            self.positions[num].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        # Random sampling approach
        length = right - left + 1
        
        for _ in range(20):  # Try 20 random samples
            idx = random.randint(left, right)
            candidate = self.arr[idx]
            
            # Count occurrences using binary search
            pos_list = self.positions[candidate]
            l = bisect.bisect_left(pos_list, left)
            r = bisect.bisect_right(pos_list, right)
            count = r - l
            
            if count >= threshold:
                return candidate
        
        return -1


# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)

Source