Watch 10 video solutions for Smallest Subarrays With Maximum Bitwise OR, a medium level problem involving Array, Binary Search, Bit Manipulation. This walkthrough by codestorywithMIK has 13,178 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |