Shortest Subarray With OR at Least K II - Practice Coding Problems

Shortest Subarray With OR at Least K II - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3], k = 2

› Output: 1

💡 Note: The subarray [2] has OR = 2 ≥ 2, and [3] has OR = 3 ≥ 2. Both have length 1, which is minimum.

Example 2 — Need Multiple Elements

$ Input: nums = [2,1,8], k = 10

› Output: 3

💡 Note: No single element ≥ 10. [2,1] gives OR = 3 < 10. Need all three: [2,1,8] gives OR = 2|1|8 = 11 ≥ 10.

Example 3 — No Solution

$ Input: nums = [1,2], k = 5

› Output: -1

💡 Note: Maximum possible OR is 1|2 = 3, which is less than k = 5. No special subarray exists.

Constraints

1 ≤ nums.length ≤ 2 × 10⁵
0 ≤ nums[i] ≤ 10⁹
0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of non-negative integers and target k

Process

Check all subarrays, compute their bitwise OR

Output

Length of shortest subarray with OR ≥ k, or -1

Key Takeaway

🎯 Key Insight: Bitwise OR only increases when adding elements, making sliding window optimization possible with bit frequency tracking.

Asked in

G Google 25 f Meta 18 a Amazon 15 M Microsoft 12

The key insight is that bitwise OR only increases (never decreases) when adding elements, making sliding window techniques applicable. The optimal approach uses bit frequency tracking to efficiently maintain OR values in O(n × log(max_value)) time. Best approach: Bit manipulation sliding window. Time: O(n × log(max_value)), Space: O(log(max_value)).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Sliding Window	O(n²)	O(1)	Use sliding window with optimized OR calculation to avoid redundant work
Bit Manipulation with Frequency Tracking	O(n × log(max_value))	O(log(max_value))	Track bit frequencies in sliding window to efficiently compute OR values
Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray and find the shortest one with OR ≥ k

Optimized Sliding Window — Algorithm Steps

Start with left=0, right=0
Extend right and update running OR
When OR ≥ k, try shrinking from left
Track minimum valid window length

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Window

Begin with each possible starting position

Extend Right

Add elements and update OR until ≥ k

Record Length

Save the current window length as candidate

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int k) {
    int minLength = INT_MAX;
    
    // Try each starting position
    for (int left = 0; left < numsSize; left++) {
        int currentOr = 0;
        // Extend window from current left position
        for (int right = left; right < numsSize; right++) {
            currentOr |= nums[right];
            
            // If we found a valid subarray
            if (currentOr >= k) {
                int length = right - left + 1;
                if (length < minLength) {
                    minLength = length;
                }
                break; // No need to extend further from this left
            }
        }
    }
    
    return minLength == INT_MAX ? -1 : minLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n times, inner shrinking can run up to n times per iteration

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for window pointers and OR value

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler