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

The problem is labeled Easy but can feel closer to Medium if you have not handled sliding windows with bit manipulation before. The brute force approach is straightforward, while the optimized method requires tracking bit contributions to correctly update the OR when shrinking the window.

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

Most implementations use a sliding window and a 32-length bit counter array. Python, Java, C++, and C# solutions iterate through bits using shifts like (num >> bit) & 1 to update counters and rebuild the OR when shrinking the window.

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

Use a sliding window with bit counting. Track how many numbers in the window contribute to each of the 32 bit positions. When the window expands, update bit counts and recompute the OR. When the OR is at least k, move the left pointer to minimize the window while updating bit counters. Each element enters and exits the window once, resulting in linear scanning with a small constant factor.

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

The most efficient approach uses a sliding window combined with bit counters. Maintain a frequency array for the 32 bits of integers and track which bits are active in the current window. Expand the window until the OR value reaches at least k, then shrink it from the left while preserving the condition. This achieves O(n * 32) time and O(32) space.

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

Bit manipulation combined with sliding window techniques frequently appears in interviews at companies like Amazon, Google, and Meta. Variants of subarray OR or AND problems are common because they test understanding of bit operations and two-pointer optimization.

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

The optimized solution primarily uses an array of size 32 to count how many numbers contribute to each bit position. This structure allows efficient updates when elements enter or leave the sliding window and helps reconstruct the current OR value.

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

The brute force method runs in O(n² * 32) time because every subarray may be explored while updating the OR value. The optimized sliding window solution processes each element once while updating up to 32 bits, giving O(n * 32) time complexity with constant extra space.

Description Hints 1 Solution Video 18:55

3095. Shortest Subarray With OR at Least K I

Easy44.9% acceptance1 company

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

Asked at 1 company

Mitsogo

Topics

Hints open one at a time

Hint 1

The constraints are small. Brute force checking all the subarrays.

18:55

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

Open solution

3095. Shortest Subarray With OR at Least K I

Asked at 1 company

Topics

Hints open one at a time

Similar problems