Solution Explanation for LeetCode 1157: Online Majority Element In Subarray

This problem requires designing a data structure that efficiently finds the majority element within a given subarray. The majority element is defined as an element appearing at least threshold times within the subarray.

The optimal approach combines several techniques:

1. Segment Tree: A segment tree is used to efficiently handle queries on subarrays. Each node in the tree represents a subarray and stores information about the candidate majority element and its count within that subarray.

2. Boyer-Moore Voting Algorithm (modified): This algorithm is adapted for the segment tree. Instead of directly finding the majority element in the entire array, it's used to find a candidate majority element in each subarray represented by a segment tree node. This candidate may not necessarily be the actual majority element but will be used for efficient query processing.

3. Binary Search: Once a candidate majority element is identified using the segment tree, binary search is used to quickly count its occurrences within the specified query range. This avoids rescanning the subarray.

Time and Space Complexity Analysis

• Initialization (MajorityChecker constructor):

  • Building the segment tree takes O(N) time, where N is the length of the input array.

  • Creating the index map d (mapping elements to their indices) takes O(N) time in the worst case.

  • Overall Time Complexity: O(N)

  • The segment tree uses O(N) space. The index map d also uses O(N) space in the worst case.

  • Overall Space Complexity: O(N)

• Query (query method):

  • Querying the segment tree takes O(log N) time.

  • Binary search on the index list for the candidate element takes O(log N) time in the worst case.

  • Overall Time Complexity: O(log N)

  • The query method uses constant extra space.

  • Overall Space Complexity: O(1)

Code Implementation (Python)

import bisect
from collections import defaultdict
 
class Node:
    __slots__ = ("l", "r", "x", "cnt")
 
    def __init__(self):
        self.l = self.r = 0
        self.x = self.cnt = 0
 
 
class SegmentTree:
    def __init__(self, nums):
        self.nums = nums
        n = len(nums)
        self.tr = [Node() for _ in range(n << 2)]
        self.build(1, 1, n)
 
    def build(self, u, l, r):
        self.tr[u].l, self.tr[u].r = l, r
        if l == r:
            self.tr[u].x = self.nums[l - 1]
            self.tr[u].cnt = 1
            return
        mid = (l + r) >> 1
        self.build(u << 1, l, mid)
        self.build(u << 1 | 1, mid + 1, r)
        self.pushup(u)
 
    def query(self, u, l, r):
        # ... (Segment Tree query logic -  same as provided in original response) ...
 
    def pushup(self, u):
        # ... (Segment Tree pushup logic - same as provided in original response) ...
 
 
 
class MajorityChecker:
    def __init__(self, arr: list[int]):
        self.tree = SegmentTree(arr)
        self.d = defaultdict(list)
        for i, x in enumerate(arr):
            self.d[x].append(i)
 
    def query(self, left: int, right: int, threshold: int) -> int:
        x, _ = self.tree.query(1, left + 1, right + 1)
        l = bisect.bisect_left(self.d[x], left)
        r = bisect.bisect_left(self.d[x], right + 1)
        return x if r - l >= threshold else -1
 

The code in other languages (Java, C++, Go) follows a very similar structure, employing the same core algorithms and data structures. The only differences are in syntax and standard library functions used for implementing segment trees, binary search, and hash maps. The core logic remains consistent across all implementations.