Problem Description

You are given a 0-indexed array nums of length n containing non-negative integers. For each starting position i (from 0 to n-1), you need to find the length of the shortest subarray that begins at position i and achieves the maximum possible bitwise OR value among all subarrays starting at i.

Let's break down what this means:

• For any position i, consider all possible subarrays that start at index i: nums[i...i], nums[i...i+1], nums[i...i+2], ..., nums[i...n-1]
• Calculate the bitwise OR for each of these subarrays
• Find the maximum bitwise OR value among all these subarrays
• Determine the shortest subarray starting at i that achieves this maximum OR value

The bitwise OR operation combines bits from numbers where the result bit is 1 if at least one of the corresponding bits in the input numbers is 1.

Your task is to return an array answer of length n where answer[i] represents the length of the minimum-sized subarray starting at index i that has the maximum possible bitwise OR value.

For example, if starting from index i, the maximum OR is achieved by the subarray nums[i...i+2], then answer[i] = 3 (since the subarray contains 3 elements).

A subarray is defined as a contiguous sequence of elements from the original array, and it must be non-empty.

Intuition

The key insight is understanding how the bitwise OR operation works: once a bit becomes 1 in the OR result, it stays 1 as we include more elements. This means the OR value can only increase or stay the same as we extend a subarray - it never decreases.

For any starting position i, the maximum possible OR value is achieved by taking the OR of all elements from i to the end of the array. However, we might reach this maximum value earlier with a shorter subarray.

To find the shortest subarray that achieves the maximum OR, we need to determine which bits contribute to the final result. A bit position contributes to the maximum OR if there exists at least one element in the range [i, n-1] that has that bit set to 1.

Working backwards from the end of the array gives us an advantage: we can track the most recent (rightmost) position where each bit was set to 1. This is crucial because:

1. When we're at position i, we already know where each bit appears next in the array (from our reverse traversal)
2. The minimum subarray length needed is determined by the farthest position we need to reach to collect all the necessary 1 bits

The algorithm uses an array f of size 32 (for 32-bit integers) where f[j] stores the most recent index where bit j was set to 1. As we move backwards:

• If the current number has bit j set, we update f[j] to the current position
• If the current number doesn't have bit j set but f[j] indicates there's a 1 for this bit position ahead, we need to extend our subarray to at least position f[j] to include that bit

The minimum subarray length starting at position i is therefore the maximum distance we need to travel to collect all the bits that appear anywhere from position i onwards.

Learn more about Binary Search and Sliding Window patterns.

Solution Approach

The solution implements a reverse traversal approach with bit manipulation to efficiently find the minimum subarray length for each starting position.

Data Structure:

• ans: An array of size n initialized with all 1s, storing the final answer for each position
• f: An array of size 32 initialized with -1, tracking the most recent position where each bit is set to 1

Algorithm Steps:

1. Initialize the tracking arrays:

   • ans = [1] * n - Each position has at least a subarray of length 1 (the element itself)
   • f = [-1] * 32 - No bits have been seen yet (using -1 as sentinel value)

2. Traverse the array in reverse from index n-1 to 0:

   For each position i:

   • Initialize t = 1 to track the minimum subarray length needed

3. Check each bit position (0 to 31):

   for j in range(32):
       if (nums[i] >> j) & 1:  # Check if bit j is set in nums[i]
           f[j] = i            # Update the position of this bit
       elif f[j] != -1:       # Bit j is not set, but exists ahead
           t = max(t, f[j] - i + 1)  # Update minimum length needed

   • If bit j is set in nums[i]: Update f[j] = i to mark this as the new rightmost position for bit j
   • If bit j is not set but f[j] != -1: This bit exists somewhere to the right, so we need to extend our subarray to include it. The length needed is f[j] - i + 1

4. Update the answer:

   • ans[i] = t stores the minimum subarray length for position i

Why this works:

• By traversing backwards, when we reach position i, array f contains the positions of all bits that appear in nums[i+1] through nums[n-1]
• The maximum OR starting from position i must include all bits that appear anywhere from i onwards
• The minimum subarray length is determined by the farthest bit we need to include
• Since OR operation is monotonic (values can only increase or stay same), once we include all necessary bits, we've achieved the maximum OR

Time Complexity: O(32n) = O(n) where n is the length of the array Space Complexity: O(32) = O(1) for the bit tracking array (not counting the output array)

Example Walkthrough

Let's walk through the solution with a small example: nums = [5, 2, 7]

First, let's understand what we're looking for:

• For index 0: subarrays are [5], [5,2], [5,2,7] with ORs of 5, 7, 7 respectively. Maximum OR is 7, achieved first by [5,2], so answer[0] = 2
• For index 1: subarrays are [2], [2,7] with ORs of 2, 7 respectively. Maximum OR is 7, achieved by [2,7], so answer[1] = 2
• For index 2: only subarray is [7] with OR of 7. So answer[2] = 1

Now let's trace through the algorithm:

Initial Setup:

• ans = [1, 1, 1] (every position starts with minimum length 1)
• f = [-1] * 32 (no bits seen yet)
• Binary representations: 5 = 101, 2 = 010, 7 = 111

Iteration 1: i = 2, nums[2] = 7 (binary: 111)

• t = 1 (minimum length tracker)
• Check bits 0-31:
  • Bit 0: 7 has bit 0 set → f[0] = 2
  • Bit 1: 7 has bit 1 set → f[1] = 2
  • Bit 2: 7 has bit 2 set → f[2] = 2
  • Bits 3-31: not set in 7, and f[j] = -1, so skip
• ans[2] = t = 1
• State: f = [2, 2, 2, -1, -1, ...]

Iteration 2: i = 1, nums[1] = 2 (binary: 010)

• t = 1
• Check bits:
  • Bit 0: 2 doesn't have bit 0, but f[0] = 2 (bit 0 exists at position 2) → Need to extend: t = max(1, 2-1+1) = 2
  • Bit 1: 2 has bit 1 set → f[1] = 1
  • Bit 2: 2 doesn't have bit 2, but f[2] = 2 (bit 2 exists at position 2) → Need to extend: t = max(2, 2-1+1) = 2
• ans[1] = t = 2 (need to reach position 2 to get all bits)
• State: f = [2, 1, 2, -1, -1, ...]

Iteration 3: i = 0, nums[0] = 5 (binary: 101)

• t = 1
• Check bits:
  • Bit 0: 5 has bit 0 set → f[0] = 0
  • Bit 1: 5 doesn't have bit 1, but f[1] = 1 (bit 1 exists at position 1) → Need to extend: t = max(1, 1-0+1) = 2
  • Bit 2: 5 has bit 2 set → f[2] = 0
• ans[0] = t = 2 (need to reach position 1 to include bit 1)

Final Result: ans = [2, 2, 1]

The key insight: When processing position 0, we discovered we need bit 1 (which only exists at position 1 or later), so the minimum subarray must extend to at least position 1, giving us length 2. This matches our expected answer!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log m) or equivalently O(n × 32) = O(n)

The algorithm iterates through the array nums once from right to left (taking O(n) time). For each element at position i, it examines all 32 bits of the number (since we're dealing with 32-bit integers). The bit examination involves:

• Checking if bit j is set in nums[i] using (nums[i] >> j) & 1 - O(1) operation
• Updating the last occurrence position f[j] if the bit is set - O(1) operation
• Computing the maximum distance if the bit is not set but has been seen before - O(1) operation

Since we perform 32 constant-time operations for each of the n elements, the total time complexity is O(n × 32) = O(n × log m), where m represents the maximum value in the array (as 32 bits can represent values up to 2^32 - 1).

Space Complexity: O(n + log m) or O(n + 32) = O(n)

The algorithm uses:

• An array ans of size n to store the results - O(n) space
• An array f of fixed size 32 to track the last occurrence of each bit position - O(32) = O(log m) space
• A few variables like i, j, t - O(1) space

The total space complexity is O(n + 32) = O(n) since n dominates the constant 32.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Bit Range Assumption

A common mistake is assuming that we only need to check a limited number of bits (e.g., only up to bit 20 or 25) instead of the full 32 bits. This can lead to incorrect results when dealing with larger numbers.

Pitfall Example:

# WRONG: Only checking 20 bits
for bit_position in range(20):  # Missing bits 20-31
    if (nums[current_index] >> bit_position) & 1:
        rightmost_bit_position[bit_position] = current_index

Solution: Always check all 32 bits for signed 32-bit integers:

# CORRECT: Check all 32 bits
for bit_position in range(32):
    if (nums[current_index] >> bit_position) & 1:
        rightmost_bit_position[bit_position] = current_index

2. Forward Traversal Instead of Backward

Attempting to solve this problem by traversing from left to right makes it much harder to track which bits are needed for the maximum OR value.

Pitfall Example:

# WRONG: Forward traversal makes tracking complex
for i in range(n):
    # Hard to know which bits appear in future positions
    # Would require multiple passes or complex bookkeeping

Solution: Use backward traversal so that when processing position i, you already know all bits that appear in positions i+1 to n-1:

# CORRECT: Backward traversal
for current_index in range(n - 1, -1, -1):
    # We already know all bits that appear to the right

3. Off-by-One Error in Length Calculation

When calculating the subarray length from position i to position j, forgetting to add 1 is a frequent error.

Pitfall Example:

# WRONG: Missing +1 in length calculation
distance_to_bit = rightmost_bit_position[bit_position] - current_index

Solution: Remember that subarray length from index i to index j is j - i + 1:

# CORRECT: Include both endpoints
distance_to_bit = rightmost_bit_position[bit_position] - current_index + 1

4. Not Handling Single Element Case

Forgetting that each position can form a subarray of length 1 with just itself, which might be the answer if the element already contains all necessary bits.

Pitfall Example:

# WRONG: Starting with 0 or not initializing
min_length = 0  # Wrong initial value

Solution: Always initialize minimum length to 1 since we're guaranteed to include at least the current element:

# CORRECT: Start with length 1
min_length = 1

5. Overwriting Bit Positions Prematurely

Updating the bit position tracker before calculating the required subarray length can lead to incorrect results.

Pitfall Example:

# WRONG: Updating before using the old value
for bit_position in range(32):
    if (nums[current_index] >> bit_position) & 1:
        rightmost_bit_position[bit_position] = current_index
    # Now we can't use the old position for calculations!
    if rightmost_bit_position[bit_position] != -1:
        # This uses the updated value, not the original
        distance_to_bit = rightmost_bit_position[bit_position] - current_index + 1

Solution: The correct approach already handles this properly by using if-elif structure:

# CORRECT: Check and update in proper order
if (nums[current_index] >> bit_position) & 1:
    rightmost_bit_position[bit_position] = current_index
elif rightmost_bit_position[bit_position] != -1:
    # Only executed if bit is NOT set in current number
    distance_to_bit = rightmost_bit_position[bit_position] - current_index + 1