Abstract / Summary

Given a list of integers and queries, find the majority element in a specified subarray for each query.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 40% (50k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided module defines a MajorityChecker class that supports fast queries for a value that appears at least a given number of times (threshold) within any sub-range of an immutable integer array. The constructor prepares auxiliary data structures, and the query method uses random sampling combined with binary search to verify candidate values efficiently.

Initialization

When an instance is created, the original array is stored unchanged. A dictionary maps each distinct element to a list containing all of its positions in ascending order. This positional index enables constant-time access to the occurrence list of any value and supports logarithmic searches later.

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

The loop iterates once over the input, guaranteeing that every index is recorded exactly once. Because the indices are appended in the order of traversal, each list is already sorted, which is essential for the binary-search step in the query routine.

Query Logic

The query method receives three parameters: the left and right bounds of the interval (inclusive) and the required threshold. It first determines how many random attempts it will make. The number of attempts is the smallest among three values: a hard cap of 25, the total length of the stored array, and the length of the queried segment. This bound prevents unnecessary work on tiny inputs while still allowing enough trials on larger ranges.

retry = min(25, len(self.data), right - left + 1)

A loop runs up to retry times. In each iteration a random index inside the interval is chosen, and the element at that position becomes a candidate.

for i in range(retry):
    pick = randint(left, right)
    n    = self.data[pick]

The candidate’s full list of positions is retrieved from the pre-computed dictionary. If the total number of occurrences of the candidate in the whole array is already less than the required threshold, the candidate cannot satisfy the query and the loop proceeds to the next random pick.

have = self.pos[n]
if len(have) >= threshold:

When the candidate passes this quick size check, two binary searches locate the first occurrence not earlier than left and the first occurrence greater than right. The standard library functions bisect_left and bisect_right perform these searches in logarithmic time because the position list is sorted.

one = bisect_left(have, left)
two = bisect_right(have, right, lo=one)

The difference two - one yields the exact count of the candidate inside the query interval. If this count meets or exceeds threshold, the candidate is returned immediately as the answer.

if two - one >= threshold:
    return n

If none of the sampled candidates fulfills the condition after all attempts, the method returns -1 to indicate the absence of any qualifying element.

return -1

Edge Cases Handled

The implementation gracefully deals with intervals that contain very few elements. When the interval length is smaller than the fixed retry limit, the retry value shrinks to the interval size, ensuring that the loop never attempts to sample an index outside the bounds.

If the threshold exceeds the length of the interval, the early size check (len(have) >= threshold) will fail for every candidate, leading directly to the final -1 without unnecessary binary searches.

When the array consists of a single distinct value, the position list for that value contains every index, so the binary-search step quickly confirms the candidate on the first iteration. Conversely, if the array contains many distinct values, the early length guard filters out most candidates before the more expensive search.

The random selection uses randint(left, right), which includes both endpoints, guaranteeing that every index in the interval has an equal chance of being examined. This uniformity ensures that the probability model underlying the fixed number of retries remains valid regardless of interval size.

Performance Optimizations

The most significant optimization is the pre-construction of the pos dictionary. By storing sorted index lists for each value, the algorithm avoids scanning the original array during queries. The binary-search calls (bisect_left and bisect_right) run in logarithmic time relative to the frequency of the candidate, which is far faster than a linear scan of the interval.

Limiting the number of random attempts to a constant (25) caps the worst-case work per query, making the method’s runtime effectively independent of the overall array size. The early guard if len(have) >= threshold eliminates candidates that cannot possibly satisfy the query, preventing needless binary searches.

Using randint for sampling provides O(1) random access to any position, and the loop exits as soon as a valid majority is found, often after just one iteration when the interval contains a dominant element. The combination of these techniques yields a solution that scales well for large static arrays with many queries.

Imagine a long row of colored blocks lined up on the floor. Each block has a number written on it, and the goal is to figure out if one specific number appears very often within a certain section of the line. Before checking, the code makes a special list for every single number. This list acts like a map showing exactly where every block of that color lives. It is like having a secret notebook that tells you where every red block is or where every blue block is.

When you ask the code to find a popular number between two spots, it starts a little game of hide and seek. It picks a random block from the section you chose and checks what number is written on it. Then, it looks at the special notebook to see how many times that same number appears in the entire row. If that number shows up often enough that it might be the winner, the code uses a fast trick called binary search. This trick quickly looks at the secret notebook to count exactly how many times that number appears just in the section you asked about. If the count is high enough to pass the test, the code announces that number as the winner. If it does not find a winner after trying a few times, it simply gives up and says it could not find anyone popular enough.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java	Go		Python
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	halfrost				Go
	JoshCrozier		JS
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality