3097. Shortest Subarray With OR at Least K II - Detailed Explanation

Problem Statement

Description:
You are given an integer array A and an integer k. Your goal is to find the length of the shortest contiguous subarray of A whose bitwise OR of all elements is at least k. If no such subarray exists, return -1.

Note:
The bitwise OR of a set of numbers is the result of OR-ing all of them together. Importantly, once a bit is set (i.e., becomes 1) in the OR result, it remains set when more numbers are OR-ed.

Example 1

• Input: A = [1, 2, 3, 4], k = 7
• Explanation:
  • Consider subarray [3, 4]:
    • 3 in binary: 011
    • 4 in binary: 100
    • 3 | 4 = 111 in binary, which equals 7.
  • The subarray [3, 4] has length 2 and is the shortest that meets the condition.
• Output: 2

Example 2

• Input: A = [8, 1, 2], k = 11
• Explanation:
  • The subarray [8, 1] gives 8 | 1 = 9, which is less than 11.
  • The only subarray that works is [8, 1, 2]:
    • 8 | 1 = 9, and 9 | 2 = 11.
  • Its length is 3.
• Output: 3

Example 3

• Input: A = [1, 1, 1], k = 2
• Explanation:
  • Any subarray will have OR equal to 1 because 1 | 1 is still 1.
  • No subarray reaches the required OR of 2.
• Output: -1

Constraints

• 1 ≤ A.length ≤ 10⁵
• 0 ≤ A[i] ≤ 10⁹
• 0 ≤ k ≤ 10⁹

Hints

1. Understanding OR:
   Remember that the bitwise OR is cumulative. If a subarray has built up some bits and you extend it, you can only add more 1’s (never remove them). This makes the OR operation “monotonic” when extending a subarray.

2. Building Subarrays Efficiently:
   A brute-force method would try every possible subarray—but that’s too slow when A is large. Instead, think about maintaining a set (or dictionary) of distinct OR values for subarrays ending at the current index. When you move to the next index, update these OR values by OR-ing with the new element.

Approach 1: Brute Force (Naive)

Explanation

• Idea:
  Check every possible contiguous subarray. For each subarray, calculate the bitwise OR of its elements. If the OR is at least k, record the subarray’s length.

• Steps:

  1. Use two nested loops: one for the starting index and one for the ending index.
  2. For each subarray, compute the OR of the elements.
  3. Keep track of the minimum subarray length meeting the condition.
  4. Return the minimum length, or -1 if no subarray qualifies.

• Drawbacks:
  This approach has a time complexity of roughly O(n²) in the worst case, which is too slow when n is large.

Approach 2: Optimized DP/Dictionary Method

Explanation

• Idea:
  For each index in the array, maintain a collection (using a dictionary) of all distinct OR values that can be achieved by subarrays ending at that index. Also, track the earliest starting index for each OR value.

• Steps:

  1. Initialization:
     • Start with an empty dictionary (let’s call it dp).
  2. Iterate Over the Array:
     • For each element A[i], create a new dictionary (new_dp) where you include the subarray that consists of just A[i] (with starting index i).
     • Then, for every OR value from the previous index stored in dp, compute the new OR by doing prev_OR | A[i] and record the smallest starting index for this OR value in new_dp.
  3. Check Condition:
     • For every OR value in new_dp, if it is at least k, update the answer with the length of the subarray (i.e., i - start + 1).
  4. Update dp:
     • Set dp = new_dp and continue.

• Why It Works:
  By iteratively extending the subarrays and merging OR values that are identical, you avoid recalculating the OR for many overlapping subarrays. Since every OR operation is “monotonic” (once a bit is set, it stays set), the number of distinct OR values is bounded by the number of bits in the numbers (typically at most 32 for 32-bit integers).

Code Solutions

Python Code