Smallest Subarrays With Maximum Bitwise OR solution and explanation
Google
9 more videos on this problem
Smallest Subarrays With Maximum Bitwise OR | Detailed Explanation | Leetcode 2411 | codestorywithMIKcodestorywithMIK · 43:48 · 13K views
2411. Smallest Subarrays With Maximum Bitwise OR | Biweekly Contest 87 | LeetCode 2411Bro Coders · 12:59 · 4K views
Smallest Subarrays With Maximum Bitwise OR | Leetcode 2411Techdose · 22:36 · 4K views
Smallest Subarrays With Maximum Bitwise OR | Leetcode 2411Techdose · 22:38 · 3K views
2411. Smallest Subarrays With Maximum Bitwise OR | Leetcode Daily - PythonLeetcode Daily · 6:08 · 1K views
Leetcode 2411. Smallest Subarrays With Maximum Bitwise OR | Sliding Window + Bitmask IntuitionStatLearn Tech · 21:57 · 698 views
2411. Smallest Subarrays With Maximum Bitwise OR (Leetcode Medium)Programming Live with Larry · 22:12 · 661 views
Daily Leetcode #1946: Jul 29, 2025 - 2411. Smallest Subarrays With Maximum Bitwise ORProgramming Live with Larry · 22:29 · 645 views
Smallest Subarrays With Maximum Bitwise OR | LeetCode 2411 - Pythonimpoldev · 10:02 · 281 views
Leetcode 2411. Smallest Subarrays With Maximum Bitwise OR - bit position check solutionCode-Yao · 14:42 · 98 views
The problem
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.
- In other words, let
Bijbe the bitwise OR of the subarraynums[i...j]. You need to find the smallest subarray starting ati, such that bitwise OR of this subarray is equal tomax(Bik)wherei <= 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] <= 109
Approach overview
Problem 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 1: Brute Force Approach
The brute force approach involves checking all possible combinations or permutations to find the desired solution. This approach is generally easy to implement but may not be efficient for large inputs due to its high computational complexity.
def functionName(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
# Perform required operation
pass
arr = [1, 2, 3, 4]
functionName(arr)import java.util.*;
public class Main {
public static void functionName(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
// Perform required operation
}
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
functionName(arr);
}
}#include <iostream>
#include <vector>
using namespace std;
void functionName(vector<int>& vec) {
for (size_t i = 0; i < vec.size(); ++i) {
for (size_t j = i + 1; j < vec.size(); ++j) {
// Perform required operation
}
}
}
int main() {
vector<int> vec = {1, 2, 3, 4};
functionName(vec);
return 0;
}function functionName(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
// Perform required operation
}
}
}
const arr = [1, 2, 3, 4];
functionName(arr);#include <stdio.h>
void functionName(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Perform required operation
}
}
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
functionName(arr, n);
return 0;
}using System;
class Program {
static void functionName(int[] arr) {
for (int i = 0; i < arr.Length; i++) {
for (int j = i + 1; j < arr.Length; j++) {
// Perform required operation
}
}
}
public static void Main() {
int[] arr = {1, 2, 3, 4};
functionName(arr);
}
}This Python code snippet demonstrates using two loops to iterate over all possible pairs in an array.
Time Complexity: O(N^2)
Space Complexity: O(1)
Approach 2: Optimized Approach with Hashing
This approach utilizes a hash map to store and quickly access elements based on certain conditions defined by the problem. It significantly helps in reducing the computation time by eliminating unnecessary iterations.
def functionName(arr):
hash_set = set()
for num in arr:
if num in hash_set:
# Found a duplicate or required condition
pass
else:
hash_set.add(num)
arr = [1, 2, 3, 4]
functionName(arr)import java.util.*;
public class Main {
public static void functionName(int[] arr) {
Set<Integer> hash = new HashSet<>();
for (int num : arr) {
if (hash.contains(num)) {
// Found a duplicate or required condition
} else {
hash.add(num);
}
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4};
functionName(arr);
}
}#include <iostream>
#include <unordered_set>
using namespace std;
void functionName(const vector<int>& vec) {
unordered_set<int> hash;
for (int num : vec) {
if (hash.count(num)) {
// Found a duplicate or required condition
} else {
hash.insert(num);
}
}
}
int main() {
vector<int> vec = {1, 2, 3, 4};
functionName(vec);
return 0;
}function functionName(arr) {
let hashSet = new Set();
for (let num of arr) {
if (hashSet.has(num)) {
// Found a duplicate or required condition
} else {
hashSet.add(num);
}
}
}
const arr = [1, 2, 3, 4];
functionName(arr);#include <stdio.h>
#include <stdbool.h>
#define MAX 1000
bool hash[MAX] = { false };
void functionName(int arr[], int n) {
for (int i = 0; i < n; i++) {
if (hash[arr[i]]) {
// Found a duplicate or required condition
} else {
hash[arr[i]] = true;
}
}
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
functionName(arr, n);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static void functionName(int[] arr) {
HashSet<int> hash = new HashSet<int>();
foreach (int num in arr) {
if (hash.Contains(num)) {
// Found a duplicate or required condition
} else {
hash.Add(num);
}
}
}
public static void Main() {
int[] arr = {1, 2, 3, 4};
functionName(arr);
}
}The Python code uses a set to store elements as they are seen, providing O(1) average time complexity for membership tests.
Time Complexity: O(N)
Space Complexity: O(N)
Approach 3: Reverse Traversal
To find the shortest subarray starting at position i that maximizes the bitwise OR operation, we need to maximize the number of 1s in the result.
We use an array f of size 32 to record the earliest position of each bit 1.
We traverse the array nums[i] in reverse order. For the j-th bit of nums[i], if it is 1, then f[j] is i. Otherwise, if f[j] is not -1, it means that a number satisfying the j-th bit as 1 is found on the right, so we update the length.
The time complexity is O(n times log m), where n is the length of the array nums, and m is the maximum value in the array nums.
function smallestSubarrays(nums: number[]): number[] {
const n = nums.length;
const ans: number[] = Array(n).fill(1);
const f: number[] = Array(32).fill(-1);
for (let i = n - 1; i >= 0; i--) {
let t = 1;
for (let j = 0; j < 32; j++) {
if ((nums[i] >> j) & 1) {
f[j] = i;
} else if (f[j] !== -1) {
t = Math.max(t, f[j] - i + 1);
}
}
ans[i] = t;
}
return ans;
}func smallestSubarrays(nums []int) []int {
n := len(nums)
f := make([]int, 32)
for i := range f {
f[i] = -1
}
ans := make([]int, n)
for i := n - 1; i >= 0; i-- {
t := 1
for j := 0; j < 32; j++ {
if ((nums[i] >> j) & 1) == 1 {
f[j] = i
} else if f[j] != -1 {
t = max(t, f[j]-i+1)
}
}
ans[i] = t
}
return ans
}impl Solution {
pub fn smallest_subarrays(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len();
let mut ans = vec![1; n];
let mut f = vec![-1; 32];
for i in (0..n).rev() {
let mut t = 1;
for j in 0..32 {
if (nums[i] >> j) & 1 != 0 {
f[j] = i as i32;
} else if f[j] != -1 {
t = t.max(f[j] - i as i32 + 1);
}
}
ans[i] = t;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(N^2) |
| Optimized Approach with Hashing | Time Complexity: O(N) |
| Reverse Traversal | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Smallest Subarrays With Maximum Bitwise OR easy or hard?
Smallest Subarrays With Maximum Bitwise OR is rated Medium difficulty. The challenge is recognizing that the maximum OR depends on the farthest occurrence of each bit rather than repeatedly computing OR values. Once that insight is clear, the implementation becomes straightforward.
Smallest Subarrays With Maximum Bitwise OR Python/Java solution
Python, Java, C++, and other languages implement the same idea: maintain an array of size 32 storing the last index of each bit. Iterate from right to left, update bit positions for the current number, and compute the farthest index needed. The resulting subarray length is that distance plus one.
How to solve Smallest Subarrays With Maximum Bitwise OR in O(n)?
Traverse the array from right to left and maintain the last seen index for each of the 32 bits. When processing index i, update the bit positions using nums[i]. The smallest subarray must extend to the farthest index among all bits needed for the maximum OR. This keeps each step limited to checking 32 bits, producing near O(n) performance.
What is the best approach for Smallest Subarrays With Maximum Bitwise OR?
The most efficient approach tracks the last position where each bit appears while scanning the array from right to left. For every index, compute how far the subarray must extend to include all bits needed for the maximum OR. This solution runs in O(n * 32) time with O(32) extra space, which is effectively linear for typical integer sizes.
Is Smallest Subarrays With Maximum Bitwise OR asked at Google/Amazon/Meta?
Bit manipulation and array dependency problems similar to this appear in interviews at companies like Amazon, Google, and Meta. Interviewers often use variants that require tracking bit contributions or optimizing subarray computations. Understanding the bit-position tracking technique is especially useful for these companies.
What data structure is used in Smallest Subarrays With Maximum Bitwise OR?
The optimized solution typically uses a fixed-size array or hash map to store the latest index where each bit (0–31) appears. This structure allows constant-time updates and quick computation of the farthest index required for the maximum OR.
What is the time complexity of Smallest Subarrays With Maximum Bitwise OR?
The brute force solution takes O(n^2) time because it expands a subarray from every starting index. The optimized approach reduces this to O(n * 32) by tracking the latest occurrence of each bit and computing the farthest required index. Since integers contain at most 32 bits, this behaves like O(n) in practice.