3380. Shortest Subarray With Or At Least K Ii¶

Difficulty: Medium

3380. Shortest Subarray With OR at Least K II

Medium

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⁹

Solution¶

class Solution {
    public int minimumSubarrayLength(int[] nums, int k) {
        int n  = nums.length;
        int pref[][] = new int[n + 1][33];
        int sum = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 32; j++) pref[i + 1][j] = pref[i][j] + ((nums[i] >> j) & 1);
        }
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++) {
            int low = i;
            int high = n - 1;
            while(low <= high) {
                int mid = low + (high - low) / 2;
                if(check(i, mid , pref, k)) {
                    ans = Math.min(ans, mid - i + 1);
                    high = mid - 1;
                }
                else low = mid + 1;
            }
        }
        if(ans == Integer.MAX_VALUE) return -1;
        return ans;
    }

    public static boolean check(int start, int end, int pref[][], int k) {
        int n = pref.length;
        int res = 0;
        for(int i = 0; i < 32; i++) {
            int temp = pref[end + 1][i] - pref[start][i];
            if(temp > 0) res += (1 << i);
        }
        return res >= k;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here