# Shortest Subarray With OR at Least K I
**Difficulty:** EASY
[External](https://leetcode.com/problems/shortest-subarray-with-or-at-least-k-i)
Canonical: https://scaleengineer.com/dsa/problems/shortest-subarray-with-or-at-least-k-i
**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`.

Note that `[2]` is also a special subarray.

**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 <= 50`
* `0 <= nums[i] <= 50`
* `0 <= k < 64`

# Approaches
## Brute-Force Subarray Enumeration
This approach exhaustively checks every possible non-empty subarray. For each subarray, it computes the bitwise OR of its elements and compares it with `k`. The length of the shortest valid subarray is tracked and returned.
**Time:** O(n³), where `n` is the number of elements in `nums`. The three nested loops lead to a cubic time complexity, which can be slow for larger inputs but is acceptable for the given constraints. · **Space:** O(1), as we only use a constant amount of extra space for variables like `minLength` and `currentOR`.
**Pros:** Very straightforward to conceptualize and implement.; Guaranteed to be correct as it checks every single possibility.
**Cons:** Highly inefficient due to its cubic time complexity.; Involves a lot of redundant computation, as the OR of a subarray is recalculated repeatedly.
### Explanation
The algorithm uses three nested loops. The outer two loops define the start (`i`) and end (`j`) indices of a subarray. The innermost loop then iterates from `i` to `j` to calculate the bitwise OR of the elements within that subarray. If this OR value is at least `k`, we update our answer with the current subarray's length if it's smaller than the minimum length found so far. After checking all subarrays, if no valid subarray was found, we return -1; otherwise, we return the minimum length.

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

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Subarray is nums[i..j]
                int currentOR = 0;
                for (int l = i; l <= j; l++) {
                    currentOR |= nums[l];
                }

                if (currentOR >= k) {
                    minLength = Math.min(minLength, j - i + 1);
                }
            }
        }

        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}
```
### Algorithm
- Initialize `minLength` to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through each possible starting index `i` from `0` to `n-1`.
- For each `i`, iterate through each possible ending index `j` from `i` to `n-1`.
- For each subarray `nums[i..j]`, calculate its bitwise OR by iterating from `i` to `j`.
- If the calculated OR is greater than or equal to `k`, update `minLength = min(minLength, j - i + 1)`.
- After all loops complete, if `minLength` remains at its initial large value, return -1. Otherwise, return `minLength`.

## Optimized Brute-Force
This approach improves on the naive brute-force method by eliminating the innermost loop. It iterates through all subarrays, but calculates the bitwise OR incrementally. For a fixed starting point, as we extend the subarray to the right, the new OR is just the previous OR combined with the new element.
**Time:** O(n²), where `n` is the number of elements in `nums`. The two nested loops result in a quadratic time complexity, which is efficient enough for the given constraints. · **Space:** O(1), as the extra space used does not depend on the input size.
**Pros:** A significant improvement in efficiency over the O(n³) approach.; Simple to implement and understand.; Optimal for the given problem constraints.
**Cons:** May be too slow for problems with much larger constraints on `n`.
### Explanation
We use two nested loops. The outer loop fixes the starting index `i` of the subarray. The inner loop iterates from `i` to the end of the array, defining the ending index `j`. A variable `currentOR` is used to keep track of the bitwise OR of the elements in the current subarray `nums[i..j]`. As `j` increments, `currentOR` is updated by OR-ing it with `nums[j]`. This avoids recalculating the OR from scratch. If at any point `currentOR` becomes greater than or equal to `k`, we update the minimum length found so far.

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

        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);
                }
            }
        }

        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}
```
### Algorithm
- Initialize `minLength` to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through each possible starting index `i` from `0` to `n-1`.
- Initialize `currentOR = 0` for the subarray starting at `i`.
- For each `i`, iterate through each possible ending index `j` from `i` to `n-1`.
- Update the OR value for the subarray `nums[i..j]`: `currentOR = currentOR | nums[j]`.
- If `currentOR >= k`, update `minLength = min(minLength, j - i + 1)`.
- After all loops complete, if `minLength` remains at its initial large value, 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
```