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.

#2411

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

按位或最大的最小子数组长度

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个最小非空子数组，它的起始位置为 i （包含这个位置），同时有最大的按位或运算值。换言之，令 B ij 表示子数组 nums…

数组二分查找位运算滑动窗口

题目描述

给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，你需要找出 nums 中一个最小非空子数组，它的起始位置为 i （包含这个位置），同时有最大的 按位或运算值 。

换言之，令 B_ij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(B_ik) ，其中 i <= k <= n - 1 。

一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。

请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且最短子数组的长度。

子数组 是数组里一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,0,2,1,3]
输出：[3,3,2,2,1]
解释：
任何位置开始，最大按位或运算的结果都是 3 。
- 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。
- 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。
- 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。
- 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。
- 下标 4 处，能得到结果 3 的最短子数组是 [3] 。
所以我们返回 [3,3,2,2,1] 。

示例 2：

输入：nums = [1,2]
输出：[2,1]
解释：
下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。
下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。
所以我们返回 [2,1] 。

提示：

n == nums.length
1 <= n <= 10⁵
0 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：逆序遍历

要找到每个以 $i$ 作为起始位置的最短子数组，满足或运算结果最大，那么必须让这个结果的 $1$ 尽可能多。

我们用一个 $32$ 位大小的数组 $f$ 来记录每一位 $1$ 最早出现的位置。

逆序遍历数组 $nums[i]$ ，对于 $nums[i]$ 数字中的第 $j$ 位，如果为 $1$ ，那么 $f[j]$ 就是 $i$ 。否则如果 $f[j]$ 不为 $-1$ ，说明右侧找到了满足第 $j$ 位为 $1$ 的数字，更新长度。

时间复杂度 $O(n \times \log m)$ 。其中 $n$ 为数组 $nums$ 的长度，而 $m$ 为数组 $nums$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

speed

复杂度分析

指标	值
时间	O(n \times \log C)
空间	O(\log C)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2401 最长优雅子数组 #2398 预算内的最多机器人数目 #2354 优质数对的数目