Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on array fundamentals.
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 <= 500 <= nums[i] <= 500 <= k < 64Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Bit Manipulation · Sliding Window
[1,2,3] 2
[2,1,8] 10
[1,2] 0
minimum-size-subarray-sum)shortest-subarray-with-sum-at-least-k)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3095: Shortest Subarray With OR at Least K I
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;
}
}
// Accepted solution for LeetCode #3095: Shortest Subarray With OR at Least K I
func minimumSubarrayLength(nums []int, k int) int {
n := len(nums)
cnt := [32]int{}
ans := n + 1
s, i := 0, 0
for j, x := range nums {
s |= x
for h := 0; h < 32; h++ {
if x>>h&1 == 1 {
cnt[h]++
}
}
for ; s >= k && i <= j; i++ {
ans = min(ans, j-i+1)
for h := 0; h < 32; h++ {
if nums[i]>>h&1 == 1 {
cnt[h]--
if cnt[h] == 0 {
s ^= 1 << h
}
}
}
}
}
if ans == n+1 {
return -1
}
return ans
}
# Accepted solution for LeetCode #3095: Shortest Subarray With OR at Least K I
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
// Accepted solution for LeetCode #3095: Shortest Subarray With OR at Least K I
impl Solution {
pub fn minimum_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
let n = nums.len();
let mut cnt = vec![0; 32];
let mut ans = n as i32 + 1;
let mut s = 0;
let mut i = 0;
for (j, &x) in nums.iter().enumerate() {
s |= x;
for h in 0..32 {
if (x >> h) & 1 == 1 {
cnt[h] += 1;
}
}
while s >= k && i <= j {
ans = ans.min((j - i + 1) as i32);
let y = nums[i];
for h in 0..32 {
if (y >> h) & 1 == 1 {
cnt[h] -= 1;
if cnt[h] == 0 {
s ^= 1 << h;
}
}
}
i += 1;
}
}
if ans > n as i32 {
-1
} else {
ans
}
}
}
// Accepted solution for LeetCode #3095: Shortest Subarray With OR at Least K I
function minimumSubarrayLength(nums: number[], k: number): number {
const n = nums.length;
let ans = n + 1;
const cnt: number[] = new Array<number>(32).fill(0);
for (let i = 0, j = 0, s = 0; j < n; ++j) {
s |= nums[j];
for (let 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 (let h = 0; h < 32; ++h) {
if (((nums[i] >> h) & 1) === 1 && --cnt[h] === 0) {
s ^= 1 << h;
}
}
}
}
return ans === n + 1 ? -1 : ans;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.