2411. Smallest Subarrays With Maximum Bitwise OR
Approach
For each bit track last index it appears; scan backward taking max rightmost bit index.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Bit manipulation uses bitwise operators (&, |, ^, ~, <<, >>) for compact and fast solutions. Key tricks: x & (x-1) clears lowest set bit, x ^ x = 0 (XOR cancellation), and bitmask DP represents subsets as integers. In C#, use int (32-bit) or long (64-bit) for bitmasking.
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: For each bit track last index it appears; scan backward taking max rightmost bit index.
// Time: O(n log max) Space: O(n)
public class Solution
{
public int[] SmallestSubarrays(int[] nums)
{
// Number of elements in the given array.
int length = nums.Length;
// Array to store the answer which is the length of smallest subarrays.
int[] answer = new int[length];
// Frequency array for each bit position (0 to 31 for 32-bit integers).
int[] latestOneBitIndices = new int[32];
// Initialize with -1, it signifies that we haven't seen a bit 1 in that position so far.
Array.Fill(latestOneBitIndices, -1);
// Start from the end of the input array and move towards the start.
for (int i = length - 1; i >= 0; --i)
{
int subarraySize = 1; // Initialize the minimum subarray size to 1 for each number.
// Check each bit position.
for (int j = 0; j < 32; ++j)
{
// If the j-th bit of the current number is set (equal to 1).
if (((nums[i] >> j) & 1) == 1)
// Update the latest index where this bit was set.
latestOneBitIndices[j] = i;
else if (latestOneBitIndices[j] != -1)
// If the bit is not set, we use the latest index where this bit was set,
// to calculate the size of the subarray.
subarraySize = Math.Max(subarraySize, latestOneBitIndices[j] - i + 1);
}
// Set the computed minimum subarray size.
answer[i] = subarraySize;
}
// Return the array containing the minimum subarray sizes.
return answer;
}
}