2411. Smallest Subarrays With Maximum Bitwise OR
Problem Description
In this problem, you're presented with an array nums
of non-negative integers. Your task is to determine, for each index i
from 0
to n - 1
, the length of the smallest subarray starting at i
that produces the maximum bitwise OR value compared to all possible subarrays starting at that same index i
. We define the bitwise OR of an array as the result of applying the bitwise OR operation to all numbers in it.
To clarify with an example, if the array was [1,2,3]
, the subarrays starting from index 0
would be [1]
, [1,2]
, and [1,2,3]
. If the maximum bitwise OR achievable is with subarray [1,2]
, and that value cannot be achieved with a smaller subarray from that index, then the length you should report for index 0
would be the length of [1,2]
which is 2
. You need to perform this computation efficiently for every index of the array.
Your final output should be an integer array answer
, where answer[i]
is the length of the smallest subarray starting at index i
with the maximum bitwise OR value.
Intuition
The solution to this problem uses a bit-manipulation trick. For each index, we know that the maximum bitwise OR subarray must extend far enough to include any bits that wouldn't otherwise be set to 1
without it. What's less intuitive is figuring out how far that is without checking every subarray.
Bitwise OR operation has an 'accumulative' property; once a bit is set to 1
, it remains 1
irrespective of the OR operations that follow. This leads us to a realization: we don't need to continue our subarray beyond the point where all bits that can be set to 1
, are set.
The insight is to iterate backwards from the end of the array, keeping track of the most recent index where each bit was set to 1
. By doing this, when we're considering a given index i
, we can look at our collection of indices, and figure out the furthest one we need to reach - this gives us the length of the minimum subarray with the maximum bitwise OR.
The process involves a 32-length array (for each bit in the integer) where we keep updating our 'latest' indices as we move from the end to the start of the array. For each number, we consider every bit, update the latest index if the bit is 1
, and find the distance to the farthest index we need to include if the bit is not set. Hence, we derive the minimum length for the maximum OR subarray starting at that index. The solution brilliantly captures the bit-level details and aggregates them into a subarray problem.
Learn more about Binary Search and Sliding Window patterns.
In a binary min heap, the minimum element can be found in:
Solution Approach
The given Python solution first initializes two arrays: ans
which will contain our result - the smallest subarray sizes, and f
to keep track of the most recent index for each of the 32 bits (representing an integer in the array).
- Iterate through each element in
nums
in reverse order (starting from the last element). - For the current element
nums[i]
, initialize a temporary variablet
with the value1
as the smallest subarray size to consider is always at least 1 (the element itself). - Iterate through each of the 32 bits (0 to 31) to check which bits are set to
1
in the current element.- If the bit at position
j
innums[i]
is set to1
, updatef[j]
to bei
. This step guarantees thatf[j]
always points to the latest indexi
where thej-th
bit was set. - If the bit at position
j
is not set innums[i]
(the value is0
), andf[j]
isn't-1
(indicating that we've seen thej-th
bit set in some higher index), then we must extend our subarray to include this bit. Thus,t
is updated to be the maximum of itself andf[j] - i + 1
which represents the length needed to include thej-th
bit.
- If the bit at position
- After checking all bits,
ans[i]
is updated with the value int
, which now represents the minimum subarray size starting at indexi
that maximizes the bitwise OR value. - Once the loop is finished, we return the
ans
array which now contains the desired subarray sizes for each index in the originalnums
array.
The solution employs bit manipulation and array indexing in an elegant way to avoid checking every possible subarray, reducing what would be a potentially quadratic-time algorithm to a linear-time solution since it iterates through the array and each bit position just once.
Which of the following is a good use case for backtracking?
Example Walkthrough
Let's walk through a simple example to illustrate the solution approach. Imagine we have the array nums = [3, 11, 7]
. The binary representations of the numbers in the array are 0011
, 1011
, and 0111
respectively.
-
Initialize
ans
array to hold the result andf
array to keep track of the most recent indices where each bit is set to1
. Both arrays have a size of 3, the length ofnums
, andf
is initialized with-1
to indicate that no indices have been visited yet:ans = [0, 0, 0]
(to be filled with results)f = [-1, -1, -1, -1]
(one entry for each bit)
-
Start iterating through
nums
in reverse order:- i=2 (Last element,
nums[2] = 0111
):- Initialize
t = 1
(the smallest subarray always includes at leastnums[i]
itself). - Check each bit:
- For bit 0: It is set, so update
f[0] = 2
. - For bit 1: It is set, so update
f[1] = 2
. - For bit 2: It is set, so update
f[2] = 2
. - For bit 3: It is not set, and
f[3]
is-1
(no previous 1's).
- For bit 0: It is set, so update
- Update
ans[2]
witht = 1
.
- Initialize
At this point:
-
ans = [0, 0, 1]
-
f = [2, 2, 2, -1]
-
i=1 (Second element,
nums[1] = 1011
):- Reset
t = 1
. - Check each bit:
- For bit 0: It is set, so update
f[0] = 1
. - For bit 1: It is set, so update
f[1] = 1
. - For bit 2: It is not set, but
f[2]
is2
, so updatet
to2 - 1 + 1 = 2
. - For bit 3: It is set, so update
f[3] = 1
.
- For bit 0: It is set, so update
- Update
ans[1]
witht = 2
.
- Reset
At this point:
-
ans = [0, 2, 1]
-
f = [1, 1, 2, 1]
-
i=0 (First element,
nums[0] = 0011
):- Reset
t = 1
. - Check each bit:
- For bit 0: It is set, so update
f[0] = 0
. - For bit 1: It is set, so update
f[1] = 0
. - For bit 2: It is not set, and
f[2]
is2
, so updatet
to the maximum oft
and(2 - 0 + 1) = 3
. - For bit 3: It is not set, and
f[3]
is1
, so updatet
to the maximum oft
and(1 - 0 + 1) = 2
.
- For bit 0: It is set, so update
- Update
ans[0]
with the maximumt = 3
.
- Reset
At this point:
ans = [3, 2, 1]
f = [0, 0, 2, 1]
- i=2 (Last element,
-
After iterating through all indices,
ans
now contains the correct answer. The final arrayans = [3, 2, 1]
represents the smallest subarray sizes starting at each indexi
that achieves the maximum bitwise OR value.
In this example, the smallest subarray starting at index 0
with the maximum bitwise OR is [3, 11, 7]
, at index 1
is [11, 7]
, and at index 2
is [7]
. The algorithm efficiently identifies these subarrays without having to examine every possible subarray, showcasing the power of bit manipulation and dynamic programming.
Solution Implementation
1from typing import List
2
3class Solution:
4 def smallestSubarrays(self, nums: List[int]) -> List[int]:
5 # Get the length of the input array
6 length = len(nums)
7
8 # Initialize the result array with 1s, as the smallest non-empty subarray is the number itself.
9 result = [1] * length
10
11 # Initialize an array to store the latest positions of bits (0 to 31) seen in the binary representation of the numbers
12 last_seen_at = [-1] * 32
13
14 # Traverse the input array in reverse order
15 for i in range(length - 1, -1, -1):
16 max_size = 1 # Initialize current size to 1 (the size of a subarray containing only nums[i])
17 # Go through each of the 32 bits to update 'last_seen_at' and calculate the subarray size
18 for j in range(32):
19 if (nums[i] >> j) & 1: # Check if bit 'j' is set in nums[i]
20 last_seen_at[j] = i # Update the position of bit 'j'
21 elif last_seen_at[j] != -1: # If bit 'j' was found at a position ahead of 'i'
22 # Update 'max_size': the size of the subarray that includes the current number and
23 # the last occurrence of every bit that is not present in the current number
24 max_size = max(max_size, last_seen_at[j] - i + 1)
25 # Record the required subarray size for the current starting index 'i'
26 result[i] = max_size
27
28 # Return the array containing the sizes of the smallest subarrays
29 return result
30
1import java.util.Arrays;
2
3class Solution {
4 public int[] smallestSubarrays(int[] nums) {
5 // Number of elements in the given array.
6 int length = nums.length;
7 // Array to store the answer which is the length of smallest subarrays.
8 int[] answer = new int[length];
9 // Frequency array for each bit position (0 to 31 for 32-bit integers).
10 int[] latestOneBitIndices = new int[32];
11 // Initialize with -1, it signifies that we haven't seen a bit 1 in that position so far.
12 Arrays.fill(latestOneBitIndices, -1);
13
14 // Start from the end of the input array and move towards the start.
15 for (int i = length - 1; i >= 0; --i) {
16 int subarraySize = 1; // Initialize the minimum subarray size to 1 for each number.
17 // Check each bit position.
18 for (int j = 0; j < 32; ++j) {
19 // If the j-th bit of the current number is set (equal to 1).
20 if (((nums[i] >> j) & 1) == 1) {
21 // Update the latest index where this bit was set.
22 latestOneBitIndices[j] = i;
23 } else if (latestOneBitIndices[j] != -1) {
24 // If the bit is not set, we use the latest index where this bit was set,
25 // to calculate the size of the subarray.
26 subarraySize = Math.max(subarraySize, latestOneBitIndices[j] - i + 1);
27 }
28 }
29 // Set the computed minimum subarray size.
30 answer[i] = subarraySize;
31 }
32 // Return the array containing the minimum subarray sizes.
33 return answer;
34 }
35}
36
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 // Function to find the smallest subarrays for each element such that each
7 // subarray's bitwise OR is at least as large as the maximum bitwise OR
8 // of any subarray starting at that element.
9 vector<int> smallestSubarrays(vector<int>& nums) {
10 int size = nums.size(); // Store the size of the input array
11 vector<int> lastIndex(32, -1); // Track the last position of each bit
12 vector<int> result(size); // This will store the answer
13
14 // Iterate through the array in reverse order to determine
15 // the smallest subarray starting at each index
16 for (int i = size - 1; i >= 0; --i) {
17 int subarraySize = 1; // Minimum subarray size is 1 (the element itself)
18
19 // Check each bit position from 0 to 31
20 for (int bit = 0; bit < 32; ++bit) {
21 if ((nums[i] >> bit) & 1) { // If the current bit is set in nums[i]
22 // Update the last position of this bit to the current index
23 lastIndex[bit] = i;
24 } else if (lastIndex[bit] != -1) {
25 // If the current bit is not set, calculate the subarraySize needed
26 // to include this bit from further elements in the array
27 subarraySize = max(subarraySize, lastIndex[bit] - i + 1);
28 }
29 }
30 // After checking all the bits, store the result subarray size
31 result[i] = subarraySize;
32 }
33 return result; // Return the final vector with smallest subarray sizes
34 }
35};
36
37// Note: Additional includes or namespace imports might be required
38// depending on the scope of the snippet and the desired coding environment.
39
1// TypeScript has its own types, so no need to import C++'s <vector>
2// Defining a function to find the smallest subarrays
3
4/**
5 * Finds the smallest subarrays for each element such that each subarray's bitwise OR
6 * is at least as large as the maximum bitwise OR of any subarray starting at that element.
7 * @param nums The input array of numbers.
8 * @returns An array of the smallest subarray sizes for each element.
9 */
10function smallestSubarrays(nums: number[]): number[] {
11 const size: number = nums.length; // Store the size of the input array
12 const lastIndex: number[] = new Array(32).fill(-1); // Track the last position of each bit, for up to 32 bits
13 const result: number[] = new Array(size); // This will store the answer
14
15 // Iterate through the array in reverse order to determine
16 // the smallest subarray starting at each index
17 for (let i = size - 1; i >= 0; --i) {
18 let subarraySize: number = 1; // Minimum subarray size is 1 (the element itself)
19
20 // Check each bit position from 0 to 31
21 for (let bit = 0; bit < 32; ++bit) {
22 if ((nums[i] >> bit) & 1) { // If the current bit is set in nums[i]
23 // Update the last position of this bit to the current index
24 lastIndex[bit] = i;
25 } else if (lastIndex[bit] !== -1) {
26 // If the current bit is not set, calculate the subarraySize needed
27 // to include this bit from further elements in the array
28 subarraySize = Math.max(subarraySize, lastIndex[bit] - i + 1);
29 }
30 }
31 // After checking all the bits, store the result subarray size
32 result[i] = subarraySize;
33 }
34 return result; // Return the final array with smallest subarray sizes
35}
36
37// Example usage:
38// const nums: number[] = [1, 2, 3, 4];
39// const result: number[] = smallestSubarrays(nums);
40// console.log(result); Output: [4, 3, 2, 1]
41
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Time and Space Complexity
The given Python code is designed to find the smallest subarrays that contain all of the bits that appear at least once to the right of each element, including the element itself.
Time Complexity
The time complexity of the given code is O(n * b)
, where n
is the length of the nums
array, and b
is the number of bits used to represent the numbers. Since the input numbers are integers and Python's integers have a fixed number of bits (which is 32 bits for standard integers), the value of b
can be considered a constant, thus simplifying the time complexity further to O(n)
.
This complexity is derived from the outer loop running n
times (from n - 1
to 0
) and the inner loop over b
bits running a constant 32 times. The algorithms only perform a fixed set of operations within the inner loop, which does not depend on n
.
Space Complexity
The space complexity of the code is O(b)
, since we are maintaining a fixed-size array f
of size 32, corresponding to the 32 bits in an integer. Space is also used for the output list ans
of size n
, but when talking about space complexity we generally do not count the space required for output, or if we do, we state the complexity as additional space beyond the required output.
If one includes the space taken by the output, then it would be O(n)
. However, since the space for the output is typically not counted, and the auxiliary space used is only the fixed-size list f
, the space complexity remains O(b)
, which reduces to O(1)
since the number of bits is constant and does not grow with the input.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.