Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a fixed start, the greatest OR is the OR of its entire suffix. To obtain it as early as possible, the subarray must reach the nearest occurrence of every bit present in that suffix. Its right endpoint is the farthest of those required positions.

Approach

Scan indices from right to left, maintaining the nearest known position for each of 32 bits. Update a bit's position when it is set in the current number. The answer is the maximum stored position minus the current index plus one, clamped to at least one. The clamp handles all-zero suffixes and unused default positions. Store the answer for every start and return the array.

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        n = len(nums)
        last = [0] * 32
        res = [0] * n

        for i in range(n - 1, -1, -1):
            for bit in range(32):
                if nums[i] & (1 << bit):
                    last[bit] = i
            res[i] = max(1, max(last) - i + 1)

        return res

Complexity analysis

Let n = nums.length and B = 32 bit positions. Time: O(Bn), which is O(n) for fixed-width integers. The returned array uses O(n) space; auxiliary space excluding it is O(B) = O(1).