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.
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.length1 <= n <= 1050 <= nums[i] <= 109Problem 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.
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.
Time Complexity: O(N^2)
Space Complexity: O(1)
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.
Time Complexity: O(N)
Space Complexity: O(N)
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.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(N^2) |
| Optimized Approach with Hashing | Time Complexity: O(N) |
| Reverse Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Expansion | O(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 Bits | O(n * 32) | O(32) | Best general solution. Efficient for large arrays since each element checks at most 32 bits. |
Smallest Subarrays With Maximum Bitwise OR | Detailed Explanation | Leetcode 2411 | codestorywithMIK • codestorywithMIK • 13,178 views views
Watch 9 more video solutions →Practice Smallest Subarrays With Maximum Bitwise OR with our built-in code editor and test cases.
Practice on FleetCode