Simple RMQ solution, beats 100% 🚀
Complexity\n- Time complexity: O(log^2(n))\n\n- Space complexity: O(n)\n\n# Code\nkotlin []\nclass MajorityChecker(private val a: IntArray) {\n    private val i
# Complexity\n- Time complexity: $$O(log^2(n))$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```kotlin []\nclass MajorityChecker(private val a: IntArray) {\n    private val indices = Array(a.max() + 1) { mutableListOf<Int>() }\n\n    init {\n        for ((index, value) in a.withIndex()) {\n            indices[value] += index\n        }\n    }\n\n    inner class Range(private val left: Int, private val right: Int, val majority: Int, val count: Int) {\n        operator fun plus(other: Range): Range {\n            if (count == 0) return other\n            if (other.count == 0) return this\n            if (other.left - right != 1 && left - other.right != 1) throw UnsupportedOperationException()\n            val newLeft = min(left, other.left)\n            val newRight = max(right, other.right)\n            val countMajority = indices.count(majority, newLeft, newRight)\n            val countOtherMajority = indices.count(other.majority, newLeft, newRight)\n            return Range(newLeft, newRight, if (countMajority > countOtherMajority) majority else other.majority, max(countMajority, countOtherMajority))\n        }\n    }\n\n    inner class RMQ {\n        private val tree = Array<Range?>(a.size * 4) { null }  // value -> count\n\n        init {\n            build(1, 0, a.lastIndex)\n        }\n\n        private fun build(v: Int, tl: Int, tr: Int) {\n            if (tl == tr) {\n                tree[v] = Range(tl, tr, a[tl], 1)\n            } else {\n                val tm = (tl + tr) / 2\n                build(v * 2, tl, tm)\n                build(v * 2 + 1, tm + 1, tr)\n                tree[v] = tree[v * 2]!! + tree[v * 2 + 1]!!\n            }\n        }\n\n        private fun query(v: Int, tl: Int, tr: Int, l: Int, r: Int): Range {\n            if (l > r) return Range(0, 0, 0, 0)\n            if (l == tl && r == tr) return tree[v]!!\n            val tm = (tl + tr) / 2\n            return query(v * 2, tl, tm, l, min(r, tm)) + query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)\n        }\n\n        fun query(left: Int, right: Int): Pair<Int, Int> {\n            val range = query(1, 0, a.lastIndex, left, right)\n            return range.majority to range.count\n        }\n    }\n\n    private val rmq = RMQ()\n\n    fun query(left: Int, right: Int, threshold: Int): Int {\n        return rmq.query(left, right).let { (value, count) -> if (count >= threshold) value else -1 }\n    }\n\n    companion object {\n        private fun List<Int>.upperBound(target: Int, left: Int = 0, right: Int = size): Int {\n            if (left >= right) return right\n            val mid = left + (right - left) / 2\n            return if (this[mid] >= target) upperBound(target, left, mid) else upperBound(target, mid + 1, right)\n        }\n\n        private fun List<Int>.lowerBound(target: Int, left: Int = 0, right: Int = size) =\n            upperBound(target, left, right).let { it - if (it < size && this[it] == target) 0 else 1 }\n\n        private fun List<Int>.count(left: Int, right: Int) = lowerBound(right) - upperBound(left) + 1\n\n        private fun Array<out List<Int>>.count(target: Int, left: Int, right: Int) = this[target].count(left, right)\n    }\n}\n```\n![image.png](https://assets.leetcode.com/users/images/68ea37ac-eb5f-4c80-8453-9a9abe934ead_1730710687.4036207.png)\n
['Array', 'Binary Search', 'Design', 'Segment Tree', 'Java', 'Kotlin']