Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2411.html
2411. Smallest Subarrays With Maximum Bitwise OR
- Difficulty: Medium.
- Related Topics: .
- Similar Questions: Merge k Sorted Lists, Bitwise ORs of Subarrays.
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
Bij
be 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.length
-
1 <= n <= 105
-
0 <= nums[i] <= 109
Solution (Java, C++, Python)
-
class Solution { public int[] smallestSubarrays(int[] nums) { TreeSet<Integer>[] ar = new TreeSet[32]; for (int i = 0; i < 32; i++) ar[i] = new TreeSet<>(); for (int i = 0; i < nums.length; i++) { for (int j = 0; j < 32; j++) { if ((nums[i] >> j & 1) == 1) ar[j].add(i); } } int ans[] = new int[nums.length]; for (int i = 0; i < nums.length; i++) { int max = i; for (TreeSet<Integer> set : ar) { if (!set.isEmpty()) { max = Math.max(max, set.first()); set.remove(i); } } ans[i] = (max - i + 1); } return ans; } } ############ class Solution { public int[] smallestSubarrays(int[] nums) { int n = nums.length; int[] ans = new int[n]; int[] f = new int[32]; Arrays.fill(f, -1); for (int i = n - 1; i >= 0; --i) { int t = 1; for (int j = 0; j < 32; ++j) { if (((nums[i] >> j) & 1) == 1) { f[j] = i; } else if (f[j] != -1) { t = Math.max(t, f[j] - i + 1); } } ans[i] = t; } return ans; } }
-
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 ############ # 2411. Smallest Subarrays With Maximum Bitwise OR # https://leetcode.com/problems/smallest-subarrays-with-maximum-bitwise-or/ class Solution: def smallestSubarrays(self, nums: List[int]) -> List[int]: N = len(nums) res = [0] * N last = [0] * 32 for i in range(N - 1, -1, -1): for k in range(32, -1, -1): if (nums[i] >> k) & 1 > 0: last[k] = i res[i] = max(1, max(last) - i + 1) return res
-
class Solution { public: vector<int> smallestSubarrays(vector<int>& nums) { int n = nums.size(); vector<int> f(32, -1); vector<int> ans(n); for (int i = n - 1; ~i; --i) { int t = 1; for (int j = 0; j < 32; ++j) { if ((nums[i] >> j) & 1) { f[j] = i; } else if (f[j] != -1) { t = 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 } func max(a, b int) int { if a > b { return a } return b }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).