Skip to main content
Talentd

Smallest Subarrays With Maximum Bitwise OR - Solution & Explanation

MediumArrayBinary SearchBit ManipulationSliding Window16 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

You are given a 0-indexed array nums of length n, consisting of non-negative integers. For each index i from 0 to n - 1, you must determine the size of the minimum sized non-empty subarray of nums starting at i (inclusive) that has the maximum possible bitwise OR.

  • In other words, let Bij be the bitwise OR of the subarray nums[i...j]. You need to find the smallest subarray starting at i, such that bitwise OR of this subarray is equal to max(Bik) where i <= k <= n - 1.

The bitwise OR of an array is the bitwise OR of all the numbers in it.

Return an integer array answer of size n where answer[i] is the length of the minimum sized subarray starting at i with maximum bitwise OR.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,0,2,1,3]
Output: [3,3,2,2,1]
Explanation:
The maximum possible bitwise OR starting at any index is 3. 
- Starting at index 0, the shortest subarray that yields it is [1,0,2].
- Starting at index 1, the shortest subarray that yields the maximum bitwise OR is [0,2,1].
- Starting at index 2, the shortest subarray that yields the maximum bitwise OR is [2,1].
- Starting at index 3, the shortest subarray that yields the maximum bitwise OR is [1,3].
- Starting at index 4, the shortest subarray that yields the maximum bitwise OR is [3].
Therefore, we return [3,3,2,2,1].

Example 2:

Input: nums = [1,2]
Output: [2,1]
Explanation:
Starting at index 0, the shortest subarray that yields the maximum bitwise OR is of length 2.
Starting at index 1, the shortest subarray that yields the maximum bitwise OR is of length 1.
Therefore, we return [2,1].

 

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 0 <= nums[i] <= 109

Approach Overview

Problem Overview: You are given an integer array nums. For every index i, compute the length of the smallest subarray starting at i whose bitwise OR equals the maximum possible OR you can obtain from any subarray starting at i. The result is an array where each position stores that minimum length.

Approach 1: Brute Force Expansion (O(nĀ²) time, O(1) space)

Start at each index i and extend the subarray to the right while maintaining a running OR value. Track the maximum OR achievable from index i by continuing until the end of the array. Once that maximum is known, iterate again from i and stop at the first position where the running OR equals this value. The length of this segment becomes the answer for index i. This method relies only on repeated iteration and the bitwise OR operation. It works but becomes slow for large inputs because each starting position may scan most of the array.

Approach 2: Optimized Bit Tracking with Hashing (O(n * 32) time, O(32) space)

The key observation: the maximum OR for a suffix depends on the farthest position where each bit appears. Maintain a structure (often an array or hash map) that stores the latest index where each bit 0..31 occurs. Traverse the array from right to left. When you process index i, update the positions for all bits present in nums[i]. For every bit that could contribute to the final OR, check its last seen position and determine how far the subarray must extend to include that bit. The answer for index i is the distance to the farthest required bit position. Because there are only 32 bits in an integer, each step performs a constant number of checks, giving an efficient linear scan.

This technique is a classic pattern in bit manipulation problems: track the latest index of each bit and compute the farthest dependency required to achieve the target OR. Instead of recomputing OR values repeatedly, you directly determine the minimal window that includes all necessary bits.

Although the window length is determined by the farthest bit occurrence rather than explicit pointer movement, the reasoning is closely related to ideas from sliding window and suffix dependency tracking in array problems.

Recommended for interviews: The optimized bit-tracking approach is the expected solution. It reduces the quadratic scan to a linear traversal with constant-bit checks. Showing the brute force approach demonstrates understanding of the OR accumulation behavior, but the optimized method shows stronger algorithmic insight and familiarity with bit-level optimizations commonly expected in mid-level interview questions.

Approach 1: Brute Force Approach

The brute force approach involves checking all possible combinations or permutations to find the desired solution. This approach is generally easy to implement but may not be efficient for large inputs due to its high computational complexity.

This C code iterates over every pair of elements in the array using nested loops, allowing you to perform the desired operation on each pair.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N^2)
Space Complexity: O(1)

Try this approach in the editor ā†’

Approach 2: Optimized Approach with Hashing

This approach utilizes a hash map to store and quickly access elements based on certain conditions defined by the problem. It significantly helps in reducing the computation time by eliminating unnecessary iterations.

This C code uses a hash table to keep track of element occurrences, allowing for efficient duplicate detection or fulfilling other conditions in O(1) time per operation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

Try this approach in the editor ā†’

Approach 3: Reverse Traversal

To find the shortest subarray starting at position i that maximizes the bitwise OR operation, we need to maximize the number of 1s in the result.

We use an array f of size 32 to record the earliest position of each bit 1.

We traverse the array nums[i] in reverse order. For the j-th bit of nums[i], if it is 1, then f[j] is i. Otherwise, if f[j] is not -1, it means that a number satisfying the j-th bit as 1 is found on the right, so we update the length.

The time complexity is O(n times log m), where n is the length of the array nums, and m is the maximum value in the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(N^2)
Space Complexity: O(1)

Optimized Approach with Hashing

Time Complexity: O(N)
Space Complexity: O(N)

Reverse Traversalā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ExpansionO(nĀ²)O(1)Good for understanding how the OR grows when extending a subarray; acceptable only for small inputs.
Bit Tracking with Hashing / Last Seen BitsO(n * 32)O(32)Best general solution. Efficient for large arrays since each element checks at most 32 bits.

Video Solution

Smallest Subarrays With Maximum Bitwise OR | Detailed Explanation | Leetcode 2411 | codestorywithMIK ā€¢ codestorywithMIK ā€¢ 13,509 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Smallest Subarrays With Maximum Bitwise OR easy or hard?
Smallest Subarrays With Maximum Bitwise OR is rated Medium difficulty. The challenge is recognizing that the maximum OR depends on the farthest occurrence of each bit rather than repeatedly computing OR values. Once that insight is clear, the implementation becomes straightforward.
Smallest Subarrays With Maximum Bitwise OR Python/Java solution
Python, Java, C++, and other languages implement the same idea: maintain an array of size 32 storing the last index of each bit. Iterate from right to left, update bit positions for the current number, and compute the farthest index needed. The resulting subarray length is that distance plus one.
How to solve Smallest Subarrays With Maximum Bitwise OR in O(n)?
Traverse the array from right to left and maintain the last seen index for each of the 32 bits. When processing index i, update the bit positions using nums[i]. The smallest subarray must extend to the farthest index among all bits needed for the maximum OR. This keeps each step limited to checking 32 bits, producing near O(n) performance.
What is the best approach for Smallest Subarrays With Maximum Bitwise OR?
The most efficient approach tracks the last position where each bit appears while scanning the array from right to left. For every index, compute how far the subarray must extend to include all bits needed for the maximum OR. This solution runs in O(n * 32) time with O(32) extra space, which is effectively linear for typical integer sizes.
Is Smallest Subarrays With Maximum Bitwise OR asked at Google/Amazon/Meta?
Bit manipulation and array dependency problems similar to this appear in interviews at companies like Amazon, Google, and Meta. Interviewers often use variants that require tracking bit contributions or optimizing subarray computations. Understanding the bit-position tracking technique is especially useful for these companies.
What data structure is used in Smallest Subarrays With Maximum Bitwise OR?
The optimized solution typically uses a fixed-size array or hash map to store the latest index where each bit (0ā€“31) appears. This structure allows constant-time updates and quick computation of the farthest index required for the maximum OR.
What is the time complexity of Smallest Subarrays With Maximum Bitwise OR?
The brute force solution takes O(n^2) time because it expands a subarray from every starting index. The optimized approach reduces this to O(n * 32) by tracking the latest occurrence of each bit and computing the farthest required index. Since integers contain at most 32 bits, this behaves like O(n) in practice.

Ready to solve this problem?

Practice Smallest Subarrays With Maximum Bitwise OR with our built-in code editor and test cases.

Practice on FleetCode
Previous

Bitwise ORs of Subarrays

Next

Longest Subarray With Maximum Bitwise AND