Abstract / Summary

Find the length of the shortest contiguous part of an array whose numbers combined using bitwise OR give the largest possible result.

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 62% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Bit Manipulation
• Sliding Window

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 Solution class implements a method smallestSubarrays that, for each position in the input list nums, returns the length of the shortest sub-array ending at that position whose bitwise OR equals the OR of the entire prefix up to that point. The algorithm proceeds in a single forward pass, maintaining per-bit state that allows it to extend previously seen sub-arrays only when necessary. By tracking the most recent index where each bit became “stable,” the method can compute the required lengths directly without revisiting earlier elements.

Determining the Bit Width

The first phase computes the number of bits required to represent the largest value in nums.

high = max(nums)
bits = 1
while (1 << bits) - 1 < high:
    bits += 1

This loop increments bits until a mask of bits ones is at least as large as high. The result is the smallest integer bits such that every number in the array fits within that many bits. This ensures that subsequent loops iterate only over relevant bit positions, avoiding unnecessary work for higher, unused bits.

Data Structures for Tracking State

Three parallel structures are created:

• need - a dictionary mapping each bit to a list of indices where that bit has not yet been set in the cumulative OR.
• last - a list where last[i] stores the most recent index that contributed a new bit to the OR for the sub-array ending at i.
• have - a list where have[i] holds the current OR value for the sub-array ending at i.

need = defaultdict(list)   # indexes where this bit isn't set
last = []                   # last index which set a bit
have = []                   # already set bits

These structures grow in lockstep with the enumeration of nums, preserving a per-position view of the evolving OR.

Main Loop - Updating Per-Bit Information

The core of the algorithm iterates over each element n together with its index i. For each element, the current value is appended to have and its index to last. Then every bit position from 0 to bits-1 is examined.

for i, n in enumerate(nums):
    have.append(n)
    last.append(i)

    for bit in range(bits):
        mask = 1 << bit
        if n & mask:
            # longer subarrays
            for x in need[bit]:
                # double check
                if (have[x] | n) != have[x]:
                    last[x]  = i
                    have[x] |= n
            need[bit].clear()
        else:
            # these bits could be ORed
            need[bit].append(i)

When the current number n contains the bit mask, the algorithm knows that any earlier sub-array that was still waiting for this bit can now be satisfied. It iterates over the indices stored in need[bit]. For each such index x, it verifies whether adding n actually changes the OR value ((have[x] | n) != have[x]). If a change occurs, last[x] is updated to the current index i, and have[x] is OR-ed with n. After processing, the list for that bit is cleared because the pending requirement has been resolved.

If n does not contain the bit, the index i is appended to need[bit], indicating that sub-arrays ending at i are still missing this particular bit and may need to be extended further.

Computing the Result

After the forward pass, each entry in last represents the farthest index that contributed a new bit to the OR for the sub-array ending at the corresponding position. The final result is derived by subtracting the start index from the end index and adding one to obtain a length.

return [ l - i + 1 for i, l in enumerate(last) ]

Because last[i] is always at least i, the expression yields a positive integer length for every position.

Edge Cases Handled

When all numbers in nums are zero, high becomes zero, and the while loop for determining bits terminates immediately with bits equal to one. The inner loop still iterates over a single bit position, and because no number ever sets that bit, every index is repeatedly added to need[0]. Since the condition n & mask never holds, last remains equal to the index itself, and the final lengths are all 1, correctly reflecting that each element forms a minimal sub-array.

If the input contains numbers with varying bit lengths, the initial calculation of bits guarantees that the loop covers exactly the necessary range. For example, an array [1, 8, 3] has a maximum value of 8 (binary 1000), leading to bits = 4. The algorithm then processes bits 0 through 3, ensuring that the high-order bit of 8 is considered while lower bits are handled for the other elements.

When a number introduces multiple new bits simultaneously, the inner loop processes each bit independently. The nested iteration over need[bit] for each set bit ensures that all pending indices are updated in a single pass, correctly handling the case where a single element resolves several outstanding requirements.

Performance Optimizations

The algorithm avoids recomputing the OR for every possible sub-array by maintaining incremental OR values in have. Updating have[x] only when a new bit is actually added prevents redundant work. The use of defaultdict(list) for need provides O(1) amortized insertion and clearing of pending indices, and the explicit clear() call discards processed entries without creating new list objects.

By limiting the outer bit loop to the exact number of bits required (bits), the method prevents unnecessary iteration over irrelevant higher bits, which could otherwise dominate runtime for large integer values. The inner loop over need[bit] processes each index at most once per bit, because after an index is removed from need[bit] it will never be revisited for that bit. This ensures that the total work across all bits remains proportional to the number of indices, rather than quadratic in the length of the input.

The final list comprehension that builds the answer runs in linear time and leverages Python’s efficient C-level iteration, contributing negligible overhead compared to the main processing loop.

Overall, the design achieves a single forward traversal with per-bit bookkeeping that scales gracefully with both the size of the input and the magnitude of the numbers involved.

Imagine you have a long row of building blocks, and each block has a secret number written on it. You want to pick a small section of these blocks to make the biggest possible number by combining all the blocks in that section together.

First, the computer looks at the biggest number in the whole row to see how many bits, or little tiny switches, it needs to represent all the numbers. It keeps track of where certain switches are turned on as it walks down the row of blocks.

When the computer looks at each block, it checks if the block helps turn on any of these switches. If a block has a switch already turned on, the computer marks that spot as a good place to stop for any previous sections that were still waiting for that switch to wake up. It remembers where the very last important switch was turned on for every starting position.

By knowing exactly where the last needed switch appeared, the computer can tell how far away that point is from where it started. This distance tells you the shortest slice of blocks you need to grab to reach the maximum possible value.

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		Java	C++		Python		TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	Rust	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	everthis	JS
	fsq			C++
	JoshCrozier	JS
	varunu28		Java
	wisdompeak			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
varunu28	Java
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