#2411

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Smallest Subarrays With Maximum Bitwise OR

Find the smallest subarrays with the maximum bitwise OR for each starting index in an array.

array binary search bit manipulation sliding window

Problem Statement

You are given a 0-indexed array nums consisting of non-negative integers. For each index i, your task is to determine the size of the smallest non-empty subarray starting at index i that yields the maximum possible bitwise OR. The bitwise OR of an array is defined as the OR of all its elements.

Return an array answer where answer[i] represents the length of the smallest subarray starting at i that has the maximum bitwise OR possible from the current subarray to the end of the array.

Examples

Example 1

Input: nums = [1,0,2,1,3]

Output: [3,3,2,2,1]

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]

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

Solution Approach

Binary Search over Answer Space

The problem can be efficiently tackled by applying binary search over the valid subarray lengths. For each starting index, search the shortest length of the subarray that produces the maximum bitwise OR. This approach narrows down the search space quickly by eliminating invalid options, reducing the complexity to O(n × log C).

Bit Manipulation and OR Operation

The key observation is that the maximum bitwise OR from a subarray depends on the bits set to 1 in the numbers. By iterating through the array and focusing on each bit position, we can progressively determine how the subarray's OR value changes. Efficient manipulation of bits allows us to optimize the search for the smallest subarrays.

Sliding Window Technique

A sliding window is used to determine the length of subarrays while maintaining the current OR value. The window expands as long as the OR value doesn't reach the maximum for that subarray. Once the OR reaches its maximum, the window can be contracted to find the minimum subarray length.

Complexity Analysis

Metric	Value
Time	O(n \times \log C)
Space	O(\log C)

The time complexity is O(n × log C), where n is the length of the array and C is the largest possible bitwise OR value. The space complexity is O(log C) due to the space needed to store the binary representations of the numbers.

What Interviewers Usually Probe

Look for the candidate's ability to implement efficient binary search within the context of a bitwise operation.
Check if the candidate understands how bit manipulation impacts the OR value in subarrays.
Evaluate the candidate's use of sliding window techniques to optimize the search for the shortest subarray.

Common Pitfalls or Variants

Common pitfalls

Candidates may attempt brute force solutions without considering efficient binary search or bit manipulation.
Not properly managing the sliding window can lead to incorrect or suboptimal subarray lengths.
Failing to handle edge cases, like arrays with only one element or all elements being zero.

Follow-up variants

Consider variations where the array elements are restricted to smaller ranges, which may simplify the bit manipulation part.
Try different approaches where the array is sorted or contains duplicate values, potentially affecting the bitwise OR result.
Modify the problem to calculate the smallest subarray with a specific target OR value instead of the maximum OR.

FAQ

What is the primary approach to solving Smallest Subarrays With Maximum Bitwise OR?

The primary approach involves using binary search to determine the smallest subarray length for each index that yields the maximum bitwise OR, combined with bit manipulation and sliding window techniques.

How does bit manipulation help in this problem?

Bit manipulation allows us to efficiently compute the OR of elements and analyze how each bit contributes to the final result, optimizing the search for the smallest subarray.

What is the time complexity of this solution?

The time complexity is O(n × log C), where n is the length of the array and C is the largest possible value for the bitwise OR.

Can this problem be solved with a brute force approach?

Yes, but a brute force solution would be inefficient, as it would require checking all possible subarrays, leading to a time complexity of O(n^2). Using binary search and bit manipulation is far more efficient.

How do sliding windows contribute to the solution?

Sliding windows allow us to expand and contract subarrays while maintaining the current OR value, helping to find the minimum subarray length that achieves the maximum bitwise OR.

terminal

Solution

Solution 1: Reverse Traversal

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n
        f = [-1] * 32
        for i in range(n - 1, -1, -1):
            t = 1
            for j in range(32):
                if (nums[i] >> j) & 1:
                    f[j] = i
                elif f[j] != -1:
                    t = max(t, f[j] - i + 1)
            ans[i] = t
        return ans

Continue Practicing

#2401 longest nice subarray #2398 maximum number of robots within budget #2354 number of excellent pairs