2411. Smallest Subarrays With Maximum Bitwise OR LeetCode Solution
In this guide, you will get 2411. Smallest Subarrays With Maximum Bitwise OR LeetCode Solution with the best time and space complexity. The solution to Smallest Subarrays With Maximum Bitwise OR problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Smallest Subarrays With Maximum Bitwise OR
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 Bij be the bitwise OR of the subarray nums[i…j]. You need to find the smallest subarray starting at i, such that bitwise OR of this subarray is equal to max(Bik) where i <= 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.
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.length
1 <= n <= 105
0 <= nums[i] <= 109
Complexity Analysis
Time Complexity: O(30n) = O(n)
Space Complexity: O(n)
2411. Smallest Subarrays With Maximum Bitwise OR LeetCode Solution in C++
class Solution {
public:
vector<int> smallestSubarrays(vector<int>& nums) {
constexpr int kMaxBit = 30;
vector<int> ans(nums.size(), 1);
// closest[j] := the closest index i s.t. the j-th bit of nums[i] is 1
vector<int> closest(kMaxBit);
for (int i = nums.size() - 1; i >= 0; --i)
for (int j = 0; j < kMaxBit; ++j) {
if (nums[i] >> j & 1)
closest[j] = i;
ans[i] = max(ans[i], closest[j] - i + 1);
}
return ans;
}
}; /* code provided by PROGIEZ */
2411. Smallest Subarrays With Maximum Bitwise OR LeetCode Solution in Java
class Solution {
public int[] smallestSubarrays(int[] nums) {
final int kMaxBit = 30;
int[] ans = new int[nums.length];
// closest[j] := the closest index i s.t. the j-th bit of nums[i] is 1
int[] closest = new int[kMaxBit];
Arrays.fill(ans, 1);
for (int i = nums.length - 1; i >= 0; --i)
for (int j = 0; j < kMaxBit; ++j) {
if ((nums[i] >> j & 1) == 1)
closest[j] = i;
ans[i] = Math.max(ans[i], closest[j] - i + 1);
}
return ans;
}
} // code provided by PROGIEZ
2411. Smallest Subarrays With Maximum Bitwise OR LeetCode Solution in Python
class Solution:
def smallestSubarrays(self, nums: list[int]) -> list[int]:
kMaxBit = 30
ans = [1] * len(nums)
# closest[j] := the closest index i s.t. the j-th bit of nums[i] is 1
closest = [0] * kMaxBit
for i in reversed(range(len(nums))):
for j in range(kMaxBit):
if nums[i] >> j & 1:
closest[j] = i
ans[i] = max(ans[i], closest[j] - i + 1)
return ans # code by PROGIEZ
