Is Shortest Subarray With OR at Least K II easy or hard?

Shortest Subarray With OR at Least K II is generally rated Medium difficulty. The main challenge is realizing that bitwise OR cannot be easily reversed when removing elements, which requires tracking bit frequencies to maintain the window efficiently.

Shortest Subarray With OR at Least K II Python/Java solution

Most implementations follow the same idea across languages: maintain two pointers and a 32-length bit counter array. Update counters when expanding or shrinking the window and recompute the OR from active bits. The logic translates directly to Python, Java, C++, C, C#, and JavaScript.

How to solve Shortest Subarray With OR at Least K II in O(n)?

Use a sliding window and maintain a count of set bits for every position from 0 to 31. When a number enters the window, increment the counters for its set bits; when it leaves, decrement them. Reconstruct the OR value from these counters and shrink the window whenever the OR is at least k. Each index is processed a constant number of times, leading to O(n * 32) complexity, which is effectively linear.

What is the best approach for Shortest Subarray With OR at Least K II?

The optimal approach uses a sliding window combined with bit counting. Maintain a frequency array for the 32 bit positions to track which bits exist in the current window. Expand the window with a right pointer and shrink it with a left pointer while recomputing the OR from active bits. This achieves O(n * 32) time and O(32) space.

Is Shortest Subarray With OR at Least K II asked at Google/Amazon/Meta?

Problems combining sliding window and bit manipulation frequently appear in interviews at companies like Amazon, Google, and Meta. Variations that require maintaining bitwise OR or AND over a dynamic window are common because they test both two-pointer reasoning and bit-level thinking.

What data structure is used in Shortest Subarray With OR at Least K II?

The main structure is a sliding window implemented with two pointers. A fixed-size array of length 32 stores the frequency of each bit position in the window. This allows efficient updates when elements are added or removed and helps reconstruct the current OR value quickly.

What is the time complexity of Shortest Subarray With OR at Least K II?

The optimized sliding window solution runs in O(n * 32) time because each element enters and leaves the window once and each update checks up to 32 bits. The brute force approach takes O(n^2 * 32) time since it evaluates all possible subarrays.

Description Hints 3 Solution Video 18:07

3097. Shortest Subarray With OR at Least K II

Medium50.5% acceptance4 companies

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 * 10⁵
0 <= nums[i] <= 10⁹
0 <= k <= 10⁹

Asked at 4 companies

Mitsogo

Google Microsoft Meta

Topics

Hints open one at a time

Hint 1

For each nums[i], we can maintain each subarray’s bitwise OR result ending with it.

Hint 2

The property of bitwise OR is that it never unsets any bits and only sets new bits

Hint 3

So the number of different results for each nums[i] is at most the number of bits 32.

18:07

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

3097. Shortest Subarray With OR at Least K II

Asked at 4 companies

Topics

Hints open one at a time

Similar problems