Smallest Subarrays With Maximum Bitwise OR

Medium
1333.

Smallest Subarrays With Maximum Bitwise OR

Smallest Subarrays With Maximum Bitwise OR is a medium coding problem on arrays, binary search and bit manipulation, asked in Amazon and Google interviews.

You are given an array nums of non-negative integers. For every index i, consider the non-empty subarrays that start at i; among them, some reach the largest possible bitwise OR.

Let answer[i] be the length of the shortest subarray starting at i whose OR equals that maximum.

Return the array answer.

Example 1

Input
nums = [4,1,0,2]
Output
[4,3,2,1]
Explanation
From index 0 the maximum OR is `4 OR 1 OR 0 OR 2 = 7`, which needs the 2 at index 3. From index 2 it is 2, reached at index 3.

Example 2

Input
nums = [0,0]
Output
[1,1]
Explanation
The maximum OR is 0 and a subarray cannot be empty.

Example 3

Input
nums = [5,2,8]
Output
[3,2,1]

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • 0 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallestSubarrays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Smallest Subarrays With Maximum Bitwise OR — Solution

Smallest Subarrays With Maximum Bitwise OR solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Smallest Subarrays With Maximum Bitwise OR is a medium coding problem on arrays, binary search and bit manipulation, asked in Amazon and Google interviews.

Problem statement

You are given an array nums of non-negative integers. For every index i, consider the non-empty subarrays that start at i; among them, some reach the largest possible bitwise OR.

Let answer[i] be the length of the shortest subarray starting at i whose OR equals that maximum.

Return the array answer.

Example 1

Input: nums = [4,1,0,2]
Output: [4,3,2,1]
Explanation: From index 0 the maximum OR is `4 OR 1 OR 0 OR 2 = 7`, which needs the 2 at index 3. From index 2 it is 2, reached at index 3.

Example 2

Input: nums = [0,0]
Output: [1,1]
Explanation: The maximum OR is 0 and a subarray cannot be empty.

Example 3

Input: nums = [5,2,8]
Output: [3,2,1]

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • 0 <= nums[i] <= 10^9

Hints for Smallest Subarrays With Maximum Bitwise OR

  1. Hint 1

    The maximum OR from i is the OR of the whole suffix nums[i..n-1] — OR never decreases as the subarray grows.

  2. Hint 2

    Each bit of that maximum must be supplied by some element. Which occurrence of a bit is the cheapest to reach?

  3. Hint 3

    Scan from the right, remembering for every bit the nearest index at or after i that has it. The subarray must reach the farthest of those nearest indices.

How to solve Smallest Subarrays With Maximum Bitwise OR

Bit by bit, the subarray starting at i must stretch to the nearest element (at or after i) carrying that bit. The answer is the farthest of these nearest positions.

Approach

  1. Keep last[b], the smallest index >= i whose element has bit b, or -1 if none; start with all -1.
  2. Walk i from n - 1 down to 0. For every bit b set in nums[i], set last[b] = i.
  3. Let far be the maximum of i and every last[b]; set answer[i] = far - i + 1.

Why it works

A subarray [i, j] has the maximum OR exactly when every bit present in the suffix appears somewhere in nums[i..j], i.e. when j >= last[b] for every bit b with last[b] != -1. The smallest such j is the maximum of those positions (and at least i, since the subarray is non-empty).

Complexity

  • Time — O(30 · n)
  • Space — O(30)

Pitfalls

  • When the suffix ORs to 0 (all zeros) the answer is 1, not 0.
  • Update last with the current element before computing far.
  • Values reach 10^9, so track 30 bits.

Reference solution

Python

from typing import List

def smallestSubarrays(nums: List[int]) -> List[int]:
    n = len(nums)
    last = [-1] * 30
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        far = i
        v = nums[i]
        for b in range(30):
            if (v >> b) & 1:
                last[b] = i
            if last[b] > far:
                far = last[b]
        ans[i] = far - i + 1
    return ans

Java

public static int[] smallestSubarrays(int[] nums) {
    int n = nums.length;
    int[] last = new int[30];
    Arrays.fill(last, -1);
    int[] ans = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int far = i;
        for (int b = 0; b < 30; b++) {
            if (((nums[i] >> b) & 1) == 1) last[b] = i;
            far = Math.max(far, last[b]);
        }
        ans[i] = far - i + 1;
    }
    return ans;
}

C++

vector<int> smallestSubarrays(vector<int>& nums) {
    int n = nums.size();
    vector<int> last(30, -1), ans(n);
    for (int i = n - 1; i >= 0; i--) {
        int far = i;
        for (int b = 0; b < 30; b++) {
            if ((nums[i] >> b) & 1) last[b] = i;
            far = max(far, last[b]);
        }
        ans[i] = far - i + 1;
    }
    return ans;
}

JavaScript

var smallestSubarrays = function(nums) {
    var n = nums.length, last = new Array(30).fill(-1), ans = new Array(n);
    for (var i = n - 1; i >= 0; i--) {
        var far = i;
        for (var b = 0; b < 30; b++) {
            if ((nums[i] >> b) & 1) last[b] = i;
            if (last[b] > far) far = last[b];
        }
        ans[i] = far - i + 1;
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search