Skip to main content
Back to problems
#3097
Medium Algorithms

Shortest subarray with or at least k ii

Array Bit Manipulation Sliding Window
50.2% acceptance
Feb 25, 2026
758
72
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.

Solution

Rust
Time O(n³)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn minimum_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
    if k == 0 { return 1; }
    // Sliding window with bit count tracking
    let n = nums.len();
    let mut bits = [0i32; 30];
    let mut l = 0;
    let mut ans = i32::MAX;
    let or_from_bits = |bits: &[i32]| -> i32 {
      (0..30).fold(0, |acc, b| acc | if bits[b] > 0 { 1 << b } else { 0 })
    };
    for r in 0..n {
      for b in 0..30 { bits[b] += (nums[r] >> b) & 1; }
      while or_from_bits(&bits) >= k {
        ans = ans.min((r - l + 1) as i32);
        for b in 0..30 { bits[b] -= (nums[l] >> b) & 1; }
        l += 1;
      }
    }
    if ans == i32::MAX { -1 } else { ans }
  }
}