Abstract / Summary

Find the shortest continuous part of an array where the OR of all numbers is at least k.

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 45% (90k+ submissions).

Typical patterns to solve this problem:

• Array
• 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 implementation defines a method that searches for the shortest contiguous sub-array whose bitwise OR is at least a given threshold k. It iterates over all possible start positions, expands each candidate sub-array while maintaining the cumulative OR, and records the minimal length when the condition is satisfied. If no sub-array meets the requirement, the method returns -1.

Initialization

The algorithm begins by creating a sentinel value that represents an unattainably large result.

result = +inf

Using positive infinity allows a straightforward comparison later: any real sub-array length will be smaller, so the first qualifying sub-array will replace the sentinel.

Outer Loop - Selecting the Start Index

The next step determines the total number of elements and iterates over each possible left boundary of a sub-array.

size = len(nums)
for i in range(size):

The variable i marks the current start index. By looping from 0 to size-1, the algorithm guarantees that every potential sub-array is considered.

Inner Loop - Expanding the Sub-array

For each start index, a fresh accumulator have is set to zero. The inner loop then walks forward, progressively incorporating each element into the cumulative OR.

have = 0
for j in range(i, size):
    have |= nums[j]

The bitwise OR operation |= updates have to reflect the OR of all elements from i through j. This incremental approach avoids recomputing the OR from scratch for each extension.

Condition Check and Early Termination

After each update, the algorithm tests whether the accumulated OR meets or exceeds the target k. When the condition becomes true, the current window length is a candidate for the answer, and the inner loop terminates early.

if have >= k:
    result = min(result, j - i + 1)
    break

The min call preserves the smallest length found so far. The break statement prevents unnecessary further expansion of the same start index, because any longer sub-array would only increase the length without improving the result.

Final Result Determination

When all start positions have been processed, the method decides whether a valid sub-array was discovered. If result still holds the sentinel value, the method returns -1; otherwise it returns the recorded minimal length.

return result if result != +inf else -1

Edge Cases Handled

The code naturally accommodates an empty input list. In that situation size is zero, the outer loop never executes, result remains +inf, and the method returns -1, indicating the absence of any qualifying sub-array.

When the threshold k is zero, the condition have >= k is satisfied immediately after the first element is OR-ed, because have starts at zero and any non-negative integer is greater than or equal to zero. Consequently the method returns a length of 1, reflecting the smallest possible sub-array.

If the array contains values that never produce an OR large enough to reach k, the inner loop will exhaust all extensions for each start index without triggering the condition. The sentinel value persists, and the final return yields -1. This behavior correctly signals that no solution exists.

The use of a cumulative OR ensures that the algorithm correctly handles cases where later elements contribute additional bits that push the OR over the threshold, even if earlier elements alone are insufficient.

Implicit Performance Optimizations

The most notable optimization is the early exit from the inner loop once the required OR is achieved. By breaking out as soon as the condition holds, the algorithm avoids scanning the remainder of the array for the current start index, reducing the amount of work performed for each successful candidate.

Maintaining the running OR in a variable (have) eliminates the need to recompute the OR of the current window from scratch on each iteration. This incremental update saves repeated bitwise operations and contributes to a leaner execution path.

The sentinel +inf combined with the min function provides a constant-time way to keep track of the best answer without additional data structures. This simplicity keeps the memory footprint minimal and the control flow straightforward.

Imagine a long row of numbered toy boxes placed in a line. Each box has a special secret number inside it. The goal is to find the smallest group of boxes sitting right next to each other that, when combined together in a magical way, make a total value that is at least as big as a target number called k.

The computer starts by looking at the very first box in the line. It picks up that box and then keeps adding the next box one by one until the total value is large enough. Once the total is big enough, the computer remembers how many boxes it used to reach that goal.

After checking all the combinations starting from that first box, the computer moves over to the second box and starts the whole process again. It repeats this pattern for every single starting position in the long line. Because it tries every possible group starting at every possible spot, it eventually finds the teeny-tiny group that uses the fewest number of boxes to reach the target.

Whenever it finds a group that is smaller than the smallest one found before, it remembers that new, better size. If it looks at every single spot and still cannot find any group that reaches the target number, it just decides that the job cannot be done.

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

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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

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