Shortest Subarray With OR at Least K II Solution in Java

Explore Solutions in Other Languages

Problem Statement

Ah, the classic problem of finding the shortest subarray with an OR value of at least K. It’s like trying to find the shortest line at the DMV—everyone wants to get to the front, but no one wants to wait in line! Imagine you’re at a buffet, and you want to grab the shortest plate of food that still has at least one of every dish. You can’t just grab a tiny plate with only mashed potatoes and call it a day; you need a little bit of everything!

In this problem, you’re given an array of integers, and your task is to find the shortest contiguous subarray such that the bitwise OR of its elements is at least K. If you can’t find such a subarray, you’ll return -1.

Code Solution


class Solution {
  public int minimumSubarrayLength(int[] nums, int k) {
    final int kMax = 50;
    final int n = nums.length;
    int ans = n + 1;
    int ors = 0;
    int[] count = new int[kMax + 1];

    for (int l = 0, r = 0; r < n; ++r) {
      ors = orNum(ors, nums[r], count);
      while (ors >= k && l <= r) {
        ans = Math.min(ans, r - l + 1);
        ors = undoOrNum(ors, nums[l], count);
        ++l;
      }
    }

    return (ans == n + 1) ? -1 : ans;
  }

  private static final int kMaxBit = 30;

  private int orNum(int ors, int num, int[] count) {
    for (int i = 0; i < kMaxBit; ++i)
      if ((num >> i & 1) == 1 && ++count[i] == 1)
        ors += 1 << i;
    return ors;
  }

  private int undoOrNum(int ors, int num, int[] count) {
    for (int i = 0; i < kMaxBit; ++i)
      if ((num >> i & 1) == 1 && --count[i] == 0)
        ors -= 1 << i;
    return ors;
  }
}

Approach Explanation

The approach used in this solution is a sliding window technique combined with bitwise operations. The idea is to maintain a window defined by two pointers, l and r, which represent the left and right ends of the subarray. As you expand the right pointer r, you calculate the OR of the current subarray. If the OR meets or exceeds K, you try to shrink the window from the left by moving the left pointer l to find the shortest valid subarray.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(n * kMaxBit)
Space Complexity O(kMax)

Real-World Example

Imagine you’re at a party, and you want to gather a group of friends to form a band. You need at least one guitarist, one drummer, and one singer (let’s say these represent the bits in your OR operation). You start gathering people (elements of the array) until you have at least one of each role (the OR value reaches K). The challenge is to do this with the fewest number of friends possible—because who wants to carry around a whole entourage when you just need a trio?

Similar Problems