Smallest Subarrays With Maximum Bitwise OR

Smallest Subarrays With Maximum Bitwise OR - Problem

You are given a 0-indexed array nums of length n, consisting of non-negative integers. For each index i from 0 to n - 1, you must determine the size of the minimum sized non-empty subarray of nums starting at i (inclusive) that has the maximum possible bitwise OR.

In other words, let B_ij be the bitwise OR of the subarray nums[i...j]. You need to find the smallest subarray starting at i, such that bitwise OR of this subarray is equal to max(B_ik) where i ≤ k ≤ n - 1.

The bitwise OR of an array is the bitwise OR of all the numbers in it.

Return an integer array answer of size n where answer[i] is the length of the minimum sized subarray starting at i with maximum bitwise OR.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,0,3,5]

› Output: [3,3,2,1]

💡 Note: Starting at index 0: maximum OR is 1|0|3|5=7, minimum length is 3 (need [1,0,3] to get OR=3, then add 5 to get 7). Starting at index 1: need [0,3,5] for maximum OR=7. Starting at index 2: need [3,5] for OR=7. Starting at index 3: only [5] gives OR=5.

Example 2 — Single Element

$ Input: nums = [8]

› Output: [1]

💡 Note: Only one element, so the minimum subarray starting at index 0 has length 1 with OR=8.

Example 3 — All Same Values

$ Input: nums = [2,2,2]

› Output: [1,1,1]

💡 Note: All elements are the same, so from each position, a single element achieves the maximum OR of 2.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [1,0,3,5] with bitwise OR operations

Find Max OR

Calculate maximum possible OR from each starting position

Find Min Length

Determine shortest subarray achieving maximum OR

Key Takeaway

🎯 Key Insight: Bitwise OR only increases or stays same, so we can efficiently find when maximum is achieved

Asked in

M Microsoft 35 G Google 28 A Amazon 22

The key insight is that bitwise OR can only increase or stay the same as we add elements. The optimal approach pre-computes maximum OR values from each position, then finds minimum lengths efficiently. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation - Track OR Changes	O(n²)	O(1)	Use bit manipulation properties to efficiently track when OR values change and stabilize
Optimized Approach - Single Pass with Bit Tracking	O(n²)	O(n)	Use the property that OR only increases or stays same, tracking when maximum OR is first achieved
Brute Force - Check All Subarrays	O(n³)	O(1)	For each starting position, try all possible ending positions to find maximum OR and minimum length

Bit Manipulation - Track OR Changes — Algorithm Steps

Track bit positions that become set as we extend subarrays
Use the monotonic property of OR to detect maximum
Optimize by recognizing when OR stabilizes

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize OR

Start with OR = 0 for current subarray

Extend and Track

Add each element and track OR progression

Find Target

Stop when OR equals maximum possible value

Code -

solution.c — C

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

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* result = (int*)malloc(numsSize * sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        int currentOr = 0;
        int maxOr = 0;
        
        // Find max OR first
        int tempOr = 0;
        for (int j = i; j < numsSize; j++) {
            tempOr |= nums[j];
        }
        maxOr = tempOr;
        
        // Find minimum length to achieve max OR
        currentOr = 0;
        for (int j = i; j < numsSize; j++) {
            currentOr |= nums[j];
            if (currentOr == maxOr) {
                result[i] = j - i + 1;
                break;
            }
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each starting position, we may need to check all remaining positions

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for bit tracking

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Bit Manipulation - Track OR Changes — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler