Smallest Subarrays With Maximum Bitwise OR — Solution
Smallest Subarrays With Maximum Bitwise OR solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Smallest Subarrays With Maximum Bitwise OR is a medium coding problem on arrays, binary search and bit manipulation, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Binary Search, Bit Manipulation, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of non-negative integers. For every index i, consider the non-empty subarrays that start at i; among them, some reach the largest possible bitwise OR.
Let answer[i] be the length of the shortest subarray starting at i whose OR equals that maximum.
Return the array answer.
Example 1
Input: nums = [4,1,0,2]
Output: [4,3,2,1]
Explanation: From index 0 the maximum OR is `4 OR 1 OR 0 OR 2 = 7`, which needs the 2 at index 3. From index 2 it is 2, reached at index 3.
Example 2
Input: nums = [0,0]
Output: [1,1]
Explanation: The maximum OR is 0 and a subarray cannot be empty.
Example 3
Input: nums = [5,2,8]
Output: [3,2,1]
Constraints
n == nums.length1 <= n <= 10^50 <= nums[i] <= 10^9
Hints for Smallest Subarrays With Maximum Bitwise OR
Hint 1
The maximum OR from
iis the OR of the whole suffixnums[i..n-1]— OR never decreases as the subarray grows.Hint 2
Each bit of that maximum must be supplied by some element. Which occurrence of a bit is the cheapest to reach?
Hint 3
Scan from the right, remembering for every bit the nearest index at or after
ithat has it. The subarray must reach the farthest of those nearest indices.
How to solve Smallest Subarrays With Maximum Bitwise OR
Bit by bit, the subarray starting at i must stretch to the nearest element (at or after i) carrying that bit. The answer is the farthest of these nearest positions.
Approach
- Keep
last[b], the smallest index>= iwhose element has bitb, or -1 if none; start with all -1. - Walk
ifromn - 1down to 0. For every bitbset innums[i], setlast[b] = i. - Let
farbe the maximum ofiand everylast[b]; setanswer[i] = far - i + 1.
Why it works
A subarray [i, j] has the maximum OR exactly when every bit present in the suffix appears somewhere in nums[i..j], i.e. when j >= last[b] for every bit b with last[b] != -1. The smallest such j is the maximum of those positions (and at least i, since the subarray is non-empty).
Complexity
- Time —
O(30 · n) - Space —
O(30)
Pitfalls
- When the suffix ORs to 0 (all zeros) the answer is 1, not 0.
- Update
lastwith the current element before computingfar. - Values reach 10^9, so track 30 bits.
Reference solution
Python
from typing import List
def smallestSubarrays(nums: List[int]) -> List[int]:
n = len(nums)
last = [-1] * 30
ans = [0] * n
for i in range(n - 1, -1, -1):
far = i
v = nums[i]
for b in range(30):
if (v >> b) & 1:
last[b] = i
if last[b] > far:
far = last[b]
ans[i] = far - i + 1
return ansJava
public static int[] smallestSubarrays(int[] nums) {
int n = nums.length;
int[] last = new int[30];
Arrays.fill(last, -1);
int[] ans = new int[n];
for (int i = n - 1; i >= 0; i--) {
int far = i;
for (int b = 0; b < 30; b++) {
if (((nums[i] >> b) & 1) == 1) last[b] = i;
far = Math.max(far, last[b]);
}
ans[i] = far - i + 1;
}
return ans;
}C++
vector<int> smallestSubarrays(vector<int>& nums) {
int n = nums.size();
vector<int> last(30, -1), ans(n);
for (int i = n - 1; i >= 0; i--) {
int far = i;
for (int b = 0; b < 30; b++) {
if ((nums[i] >> b) & 1) last[b] = i;
far = max(far, last[b]);
}
ans[i] = far - i + 1;
}
return ans;
}JavaScript
var smallestSubarrays = function(nums) {
var n = nums.length, last = new Array(30).fill(-1), ans = new Array(n);
for (var i = n - 1; i >= 0; i--) {
var far = i;
for (var b = 0; b < 30; b++) {
if ((nums[i] >> b) & 1) last[b] = i;
if (last[b] > far) far = last[b];
}
ans[i] = far - i + 1;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search