3097. Shortest Subarray With OR at Least K II

MediumBit ManipulationArraySliding Window

Problem Description

You are given an array nums of non-negative integers and an integer k.

An array is called special if the bitwise OR of all of its elements is at least k.

Return the length of the shortest special non-empty subarray of nums, or return -1 if no special subarray exists.

Intuition

The given problem requires finding the shortest subarray in the nums array such that the bitwise OR of the subarray is at least k. Intuitively, as you consider more elements from nums, the result of the bitwise OR can only increase since any bit set in additional elements would propagate to the result.

The problem is approached using a two pointers technique, which efficiently manages variable subarray sizes:

Initialize Pointers and States: Use two pointers i and j to denote the current subarray boundaries in nums. Start both pointers at the beginning. Maintain a variable s to store the current subarray's bitwise OR result and an array cnt to count the number of times each bit is set in the subarray.
Expand the Subarray: Move the second pointer j to the right through nums, updating s and the cnt array to reflect the addition of the new element. As the subarray includes more elements, s can either stay the same or increase.
Check Conditions: If at any j value, the s meets or exceeds k, a candidate for the shortest subarray is found. Update the answer with the length of this subarray, then attempt to shrink the subarray from the left (incrementing i) while maintaining the requirement s >= k.
Optimize: Throughout this process, adjust the cnt entries and re-evaluate s as elements are removed from the left to ensure it still meets the minimum requirement.

This method efficiently finds the shortest valid subarray by ensuring each element in nums is only considered twice: once during expansion with j and potentially during shrinking with i.

Learn more about Sliding Window patterns.

Solution Approach

To solve the problem of finding the shortest special subarray with a bitwise OR of at least k, we utilize a two-pointer technique combined with counting. Here’s a detailed walk-through of the algorithm:

Initialization:
- Let n be the length of nums, and initialize cnt as an array of zeroes with a size of 32. cnt is used to hold the counts of each bit position being set across the current subarray.
- Set ans to n + 1 to represent the length of the shortest subarray found, initialized to an unrealistically large value to facilitate finding the minimum.
- Use s to track the current bitwise OR value of the subarray, and i to maintain the start index of the subarray under consideration.
Iterate with the Right Pointer (j):
- Iterate through nums with index j, adding each element x to the subarray.
- Update s by performing s |= x, incorporating the current element into the subarray’s OR value.
- Update the cnt array by iterating through each bit position (0 to 31) and increment the count if the current element x has that bit set.
Check Validity and Shrink with Left Pointer (i):
- While s is at least k and i <= j, the current subarray meets the requirement:
  - Update ans as the smaller value between ans and the current subarray length (j - i + 1).
  - Remove the element at i from the subarray by adjusting cnt: Decrement each bit’s count present in the element being removed.
  - If decrementing the count causes a bit’s count to drop to zero, update s by clearing that bit: s ^= 1 << h.
  - Increment i to further shorten the subarray from the left end.
Result:
- After iterating through all elements, return ans if a valid subarray is found, else return -1 if ans remains larger than n.

This approach efficiently manages the bit manipulation using counting and exploits the non-decreasing nature of bitwise OR operations on arrays, ensuring that each potential subarray is considered precisely once.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the array nums = [1, 2, 3, 4] and k = 3. We need to find the shortest subarray such that the bitwise OR of its elements is at least 3.

Initialization:
- Set the length of nums as n = 4.
- Initialize the cnt array with 32 zeroes to keep track of the bit count.
- Initialize ans with 5 (one more than n).
- Set s = 0 to track the current OR value, and i = 0 as the starting index.
Iterate with the Right Pointer (j):
- For j = 0 (num = 1):
  - Update s: s |= 1 results in s = 1.
  - Update cnt: Only bit 0 is set in 1, so increment cnt[0].
  - s is not at least 3, so continue.
- For j = 1 (num = 2):
  - Update s: s |= 2 results in s = 3.
  - Update cnt: Bits 1 (in 2) is set, so increment cnt[1].
  - s = 3 meets the condition, so update ans = 2 (j - i + 1 = 1 - 0 + 1).
  - Try to shrink: Remove nums[i], i = 0 (num = 1):
    - Decrement cnt[0], results in s = 2.
    - Increment i to 1.
  - Continue, as s < 3.
- For j = 2 (num = 3):
  - Update s: s |= 3 results in s = 3.
  - Update cnt: Bits 0 and 1 (in 3) are set, increment cnt[0] and cnt[1].
  - s = 3 meets the condition, update ans = 2 (j - i + 1 = 2 - 1 + 1).
  - Shrink: Remove nums[i], i = 1 (num = 2):
    - Decrement cnt[1], results in s = 1.
    - Increment i to 2.
  - Continue, as s < 3.
- For j = 3 (num = 4):
  - Update s: s |= 4 results in s = 5.
  - Update cnt: Bit 2 (in 4) is set, increment cnt[2].
  - s = 5 greater than 3, update ans = 2 (j - i + 1 = 3 - 2 + 1).
  - Shrink: Remove nums[i], i = 2 (num = 3):
    - Decrement cnt[0] and cnt[1], results in s = 4.
    - Increment i to 3.
  - s still at least 3, update ans = 1.
Final Result:
- The shortest subarray with a bitwise OR of at least k = 3 is of length 1, corresponding to the subarray [4].

Thus, the solution returns 1.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumSubarrayLength(self, nums: List[int], k: int) -> int:
5        n = len(nums)  # Get the length of the input list
6        count = [0] * 32  # Initialize a list to count the number of 1s for each bit position
7        ans = n + 1  # Initialize answer to be greater than the maximum possible subarray length
8        current_or = i = 0  # Initialize OR accumulator and start index of the window
9
10        # Iterate through the list
11        for j, num in enumerate(nums):
12            current_or |= num  # Add current number to the OR accumulator
13            # Update count of 1s for each bit position
14            for bit_position in range(32):
15                if num >> bit_position & 1:  # Check if the bit at `bit_position` is set
16                    count[bit_position] += 1
17          
18            # Move the start of the window to reduce the size while maintaining OR >= k
19            while current_or >= k and i <= j:
20                ans = min(ans, j - i + 1)  # Update minimum subarray length
21                start_num = nums[i]  # Get the number at the start of the window
22                # Update count and OR value by removing start_num
23                for bit_position in range(32):
24                    if start_num >> bit_position & 1:  # Check if the bit at `bit_position` is set
25                        count[bit_position] -= 1
26                        if count[bit_position] == 0:  # If there are no more 1s in this position
27                            current_or ^= 1 << bit_position  # Remove the impact of this bit from the OR
28                i += 1  # Move the start of the window forward
29
30        # Return -1 if no valid subarray was found, else return the minimum length
31        return -1 if ans > n else ans
32

1class Solution {
2    public int minimumSubarrayLength(int[] nums, int k) {
3        int n = nums.length; // Length of the nums array
4        int[] cnt = new int[32]; // Count of 1 bits in each bit position
5        int ans = n + 1; // Initialize answer with a large number (larger than possible subarray length)
6      
7        for (int i = 0, j = 0, bitwiseOrSum = 0; j < n; ++j) {
8            // Update the running bitwise OR sum with the current element
9            bitwiseOrSum |= nums[j];
10          
11            // Increment the count of 1 bits for each position in the current number
12            for (int bitPosition = 0; bitPosition < 32; ++bitPosition) {
13                if ((nums[j] >> bitPosition & 1) == 1) {
14                    ++cnt[bitPosition];
15                }
16            }
17          
18            // Slide the window from the left if the current bitwise OR is greater than or equal to k
19            for (; bitwiseOrSum >= k && i <= j; ++i) {
20                // Update the answer with the minimum length of the valid subarray
21                ans = Math.min(ans, j - i + 1);
22              
23                // Decrement the count of 1 bits for each position in the leftmost element of the window
24                for (int bitPosition = 0; bitPosition < 32; ++bitPosition) {
25                    if ((nums[i] >> bitPosition & 1) == 1) {
26                        if (--cnt[bitPosition] == 0) {
27                            // If no more 1s exist in a bit position, remove that bit from the OR using XOR
28                            bitwiseOrSum ^= 1 << bitPosition;
29                        }
30                    }
31                }
32            }
33        }
34      
35        // If the answer hasn't been updated, return -1. Otherwise, return the minimum length found.
36        return ans > n ? -1 : ans;
37    }
38}
39

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int minimumSubarrayLength(std::vector<int>& nums, int k) {
7        int n = nums.size();
8        int bit_count[32] = {}; // Array to keep track of the count of bits set at each position
9        int result = n + 1; // Initialize the result to a large value (larger than any possible subarray)
10      
11        // Two pointers for the sliding window, and a variable s to store bitwise OR of the current window
12        for (int left = 0, right = 0, current_or = 0; right < n; ++right) {
13            current_or |= nums[right]; // Add nums[right] to the current OR
14          
15            // Update the count of each bit set in nums[right]
16            for (int bit = 0; bit < 32; ++bit) {
17                if ((nums[right] >> bit & 1) == 1) {
18                    ++bit_count[bit];
19                }
20            }
21          
22            // Shrink the window from the left as long as the current OR is >= k
23            while (current_or >= k && left <= right) {
24                result = std::min(result, right - left + 1); // Update the result with the minimum length
25              
26                // Update the bit counts and adjust the current OR
27                for (int bit = 0; bit < 32; ++bit) {
28                    if ((nums[left] >> bit & 1) == 1) {
29                        if (--bit_count[bit] == 0) {
30                            current_or ^= 1 << bit; // Remove the bit from current OR if it becomes 0 in the window
31                        }
32                    }
33                }
34                ++left; // Move left pointer to shrink the window
35            }
36        }
37      
38        return result > n ? -1 : result; // If no valid subarray was found, return -1
39    }
40};
41

1/**
2 * Finds the minimum length of a subarray such that the bitwise OR of its elements is at least k.
3 *
4 * @param nums - An array of positive integers.
5 * @param k - The target integer for the bitwise OR operation.
6 * @returns The length of the smallest subarray that meets the condition, or -1 if none exists.
7 */
8function minimumSubarrayLength(nums: number[], k: number): number {
9    const n = nums.length;
10    let ans = n + 1; // Initialize the answer with a large value.
11    const cnt: number[] = new Array<number>(32).fill(0); // To count bit positions set across the window.
12  
13    // Two pointers technique, i and j, to explore subarrays.
14    for (let i = 0, j = 0, s = 0; j < n; ++j) {
15        // Include nums[j] in the current subarray's bitwise OR.
16        s |= nums[j];
17      
18        // Update the bit count for each bit position in nums[j].
19        for (let h = 0; h < 32; ++h) {
20            if (((nums[j] >> h) & 1) === 1) {
21                ++cnt[h];
22            }
23        }
24      
25        // Try to shrink the window from the left while maintaining s >= k.
26        while (s >= k && i <= j) {
27            // Update the minimum length of subarray found.
28            ans = Math.min(ans, j - i + 1);
29          
30            // Remove nums[i] from the current subarray's bitwise OR.
31            for (let h = 0; h < 32; ++h) {
32                if (((nums[i] >> h) & 1) === 1 && --cnt[h] === 0) {
33                    s ^= 1 << h; // Update the OR value with the removal of nums[i].
34                }
35            }
36            ++i; // Shrink the window from the left.
37        }
38    }
39  
40    // If no valid subarray was found, return -1.
41    return ans === n + 1 ? -1 : ans;
42}
43

Time and Space Complexity

The time complexity of the code is O(n * 32), where n is the length of the array nums. The nested loop runs for each element in nums, and for each element, the inner loop iterates 32 times (for each bit in a 32-bit integer).

The space complexity of the code is O(1). The space used is constant, with the main space-consuming components being the cnt array of size 32 and a few integer variables.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know