# Shortest Subarray With OR at Least K II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shortest-subarray-with-or-at-least-k-ii)
Canonical: https://scaleengineer.com/dsa/problems/shortest-subarray-with-or-at-least-k-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
**Companies:** [Mitsogo](https://scaleengineer.com/companies/mitsogo)
---
## Problem
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_.

**Example 1:**

**Input:** nums = \[1,2,3\], k = 2

**Output:** 1

**Explanation:**

The subarray `[3]` has `OR` value of `3`. Hence, we return `1`.

**Example 2:**

**Input:** nums = \[2,1,8\], k = 10

**Output:** 3

**Explanation:**

The subarray `[2,1,8]` has `OR` value of `11`. Hence, we return `3`.

**Example 3:**

**Input:** nums = \[1,2\], k = 0

**Output:** 1

**Explanation:**

The subarray `[1]` has `OR` value of `1`. Hence, we return `1`.

**Constraints:**

* `1 <= nums.length <= 2 * 105`
* `0 <= nums[i] <= 109`
* `0 <= k <= 109`

# Approaches
## Brute Force Approach
This approach systematically checks every possible non-empty subarray within the `nums` array. For each subarray, it calculates the bitwise OR of its elements and checks if this value is at least `k`. It keeps track of the minimum length of such a subarray found so far.
**Time:** O(N^2), where N is the number of elements in `nums`. There are two nested loops to iterate through all subarrays starting at `i`. · **Space:** O(1) extra space, as we only use a few variables to store the minimum length and the current OR value.
**Pros:** Simple to understand and implement.; It's a good starting point for developing more efficient solutions.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 2 * 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
The brute-force method iterates through all possible start and end points of a subarray. A naive implementation would re-calculate the OR for each subarray from scratch, leading to an O(N^3) complexity. However, this can be easily optimized. For a fixed starting point `i`, we can extend the subarray by moving the endpoint `j` from `i` to the end of the array. The bitwise OR of the new, longer subarray `nums[i...j]` can be calculated in O(1) time from the OR of the previous subarray `nums[i...j-1]`. This optimization reduces the complexity to O(N^2).

```java
class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLength = n + 1;

        for (int i = 0; i < n; i++) {
            int currentOr = 0;
            for (int j = i; j < n; j++) {
                currentOr |= nums[j];
                if (currentOr >= k) {
                    minLength = Math.min(minLength, j - i + 1);
                    // Optimization: once we find a valid subarray starting at i,
                    // any longer one is not needed for the shortest length.
                    break; 
                }
            }
        }

        return minLength > n ? -1 : minLength;
    }
}
```
### Algorithm
- Initialize `minLength` to a value larger than any possible subarray length, like `nums.length + 1`.
- Iterate through the array with an index `i` from `0` to `n-1`, representing the start of a subarray.
- For each `i`, start a nested loop with an index `j` from `i` to `n-1`, representing the end of the subarray.
- Maintain a variable `currentOr` for the subarray `nums[i...j]`. Initialize it to `0` before the inner loop.
- In the inner loop, update `currentOr` by ORing it with `nums[j]`: `currentOr |= nums[j]`.
- After updating, check if `currentOr >= k`.
- If the condition is met, you've found a special subarray of length `j - i + 1`. Update `minLength = min(minLength, j - i + 1)`.
- As an optimization, since we are looking for the shortest subarray, once a special subarray starting at `i` is found, any longer subarray starting at `i` is not of interest. So, we can `break` the inner loop and proceed to the next starting index `i`.
- After the loops complete, if `minLength` is still its initial large value, it means no special subarray was found. Return `-1`.
- Otherwise, return `minLength`.

## Sliding Window with Bit Counts
A more efficient solution uses the sliding window technique. A standard sliding window is hard to apply directly because removing an element from the left of the window (to calculate the new OR) is not a simple operation. To overcome this, we can maintain the count of set bits for each bit position (0 to 30) within the current window. This allows us to efficiently add and remove elements while keeping track of the window's total bitwise OR.
**Time:** O(N * D), where N is the length of `nums` and D is the number of bits in the integers (approximately 31). Both `right` and `left` pointers traverse the array at most once. For each element added or removed, we perform a constant number of bit operations (D). Thus, the complexity is effectively linear, O(N). · **Space:** O(1), as the `bitCounts` array has a fixed size (31), which is independent of the input size N.
**Pros:** Highly efficient with a time complexity that is effectively linear in the size of the input array.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** The logic is more complex than the brute-force approach.; Requires careful handling of bit manipulation and window shrinking logic.
### Explanation
This approach maintains a sliding window `[left, right]` and a `bitCounts` array. The `bitCounts[p]` entry stores how many numbers in the current window have the `p`-th bit set. As we slide the window's right boundary, we update `bitCounts`. Then, we check if the window's OR value (which can be reconstructed from `bitCounts`) is at least `k`. If it is, we've found a candidate subarray. We then try to shrink the window from the left, updating `bitCounts` accordingly, to find the smallest possible valid window ending at the current `right` position. This process ensures that for each `right`, we find the shortest valid subarray ending at `right`.

```java
class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLength = n + 1;
        int left = 0;
        int[] bitCounts = new int[31];

        for (int right = 0; right < n; right++) {
            // Add nums[right] to the window by updating bit counts
            for (int i = 0; i < 31; i++) {
                if (((nums[right] >> i) & 1) == 1) {
                    bitCounts[i]++;
                }
            }

            // While the window is valid, update minLength and shrink from the left
            while (left <= right) {
                int currentOr = 0;
                for (int i = 0; i < 31; i++) {
                    if (bitCounts[i] > 0) {
                        currentOr |= (1 << i);
                    }
                }

                if (currentOr >= k) {
                    minLength = Math.min(minLength, right - left + 1);
                    // Shrink window from the left
                    for (int i = 0; i < 31; i++) {
                        if (((nums[left] >> i) & 1) == 1) {
                            bitCounts[i]--;
                        }
                    }
                    left++;
                } else {
                    // Window's OR is too small, cannot shrink further
                    break;
                }
            }
        }

        return minLength > n ? -1 : minLength;
    }
}
```
### Algorithm
- Initialize `minLength` to `nums.length + 1`, a `left` pointer to `0`, and an integer array `bitCounts` of size 31 to all zeros. This array will track the number of elements in the current window that have a specific bit set.
- Iterate through the array with a `right` pointer from `0` to `n-1`.
- For each element `nums[right]`, 'add' it to the sliding window. This is done by iterating from bit `0` to `30` and incrementing `bitCounts[p]` if the `p`-th bit is set in `nums[right]`.
- After expanding the window to include `nums[right]`, enter a `while` loop that checks if the current window `[left, right]` is 'special' and tries to shrink it from the left.
- Inside the `while` loop, first calculate the `currentOr` of the window `[left, right]` by checking `bitCounts`. If `bitCounts[p] > 0`, the `p`-th bit is set in `currentOr`.
- If `currentOr >= k`:
    - The window is special. Update `minLength = min(minLength, right - left + 1)`.
    - Shrink the window from the left: 'remove' `nums[left]` by decrementing the corresponding counts in `bitCounts`, and then increment the `left` pointer.
- If `currentOr < k`:
    - The window is not special. We cannot shrink it further and still satisfy the condition. `break` the `while` loop and continue expanding the window by incrementing `right`.
- After the main loop finishes, if `minLength` has not been updated, return `-1`. Otherwise, return `minLength`.

# Solutions
### Java

```java
class Solution {
public
  int minimumSubarrayLength(int[] nums, int k) {
    int n = nums.length;
    int[] cnt = new int[32];
    int ans = n + 1;
    for (int i = 0, j = 0, s = 0; j < n; ++j) {
      s |= nums[j];
      for (int h = 0; h < 32; ++h) {
        if ((nums[j] >> h & 1) == 1) {
          ++cnt[h];
        }
      }
      for (; s >= k && i <= j; ++i) {
        ans = Math.min(ans, j - i + 1);
        for (int h = 0; h < 32; ++h) {
          if ((nums[i] >> h & 1) == 1) {
            if (--cnt[h] == 0) {
              s ^= 1 << h;
            }
          }
        }
      }
    }
    return ans > n ? -1 : ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumSubarrayLength(vector<int> &nums, int k) {
    int n = nums.size();
    int cnt[32]{};
    int ans = n + 1;
    for (int i = 0, j = 0, s = 0; j < n; ++j) {
      s |= nums[j];
      for (int h = 0; h < 32; ++h) {
        if ((nums[j] >> h & 1) == 1) {
          ++cnt[h];
        }
      }
      for (; s >= k && i <= j; ++i) {
        ans = min(ans, j - i + 1);
        for (int h = 0; h < 32; ++h) {
          if ((nums[i] >> h & 1) == 1) {
            if (--cnt[h] == 0) {
              s ^= 1 << h;
            }
          }
        }
      }
    }
    return ans > n ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minimumSubarrayLength(self, nums: List[int], k: int) -> int: n = len(nums) cnt = [0] * 32 ans = n + 1 s = i = 0 for j, x in enumerate(nums): s |= x for h in range(32): if x >> h & 1: cnt[h] += 1 while s >= k and i <= j: ans = min(ans, j - i + 1) y = nums[i] for h in range(32): if y >> h & 1: cnt[h] -= 1 if cnt[h] == 0: s ^= 1 << h i += 1 return - 1 if ans > n else ans

```