[Leetcode] 2411. Smallest Subarrays With Maximum Bitwise OR

https://leetcode.com/problems/smallest-subarrays-with-maximum-bitwise-or/description/?envType=daily-question&envId=2025-07-29

initial

very obvious n^2 sol but there should be eff way. Actually no way i could have done this cuz u have to understand bit well (well actually i kinda thought about it but didnt know how to impl)

we need an index list to know which bits of 1s we need to make the current number the max OR value. As we iterate from back, we see which bit is set as 1 in the previous indexes as the minimum length would be max(1, max(index_list)-i+1).

revisited:
so key idea is that the max or value starting at index i is determined by all the bits that appear from i to end of list. Each bits lives in the rightmost side of list so the furthest bit that is on the right should be attained via max(last).

For example
[1,0,2,1,3]
last's indexes are bit indexes and the values are the index of nums list where that number provides the bit 1 value
Initially: last = [0, 0, 0] (for bits 0, 1, 2)

i=4: A[4]=3=011 (bits 0 and 1 are set)
last[0] = 4, last[1] = 4 → last = [4, 4, 0]
res[4] = max(1, max([4,4,0]) - 4 + 1) = max(1, 4-4+1) = 1, so last[0]=4, which means bit 0 LSB is set as 1 as provided by the nums[4] number. last[1]=4, which means bit 1 is set as 1 and is provide by nums[4] number

i=3: A[3]=1=001 (bit 0 is set)
last[0] = 3 → last = [3, 4, 0]
res[3] = max(1, max([3,4,0]) - 3 + 1) = max(1, 4-3+1) = 2

i=2: A[2]=2=010 (bit 1 is set)
last[1] = 2 → last = [3, 2, 0]
res[2] = max(1, max([3,2,0]) - 2 + 1) = max(1, 3-2+1) = 2

i=1: A[1]=0=000 (no bits set)
last unchanged → last = [3, 2, 0]
res[1] = max(1, max([3,2,0]) - 1 + 1) = max(1, 3-1+1) = 3

i=0: A[0]=1=001 (bit 0 is set)
last[0] = 0 → last = [0, 2, 0]
res[0] = max(1, max([0,2,0]) - 0 + 1) = max(1, 2-0+1) = 3

sol

2 mistakes i made was

j<<1

this is wrong. We should be shifting 1 by j many times for the mask

1<<j

to give us 001, 010, 110 as we iterate j

another was

wrong:
last=[0 *32]

correct:
last=[0]*32

the wrong way was doing literally 0*32 and puttign 1 value into the list.

class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        last=[0 for _ in range(32)]
        n=len(nums)
        ans=[0]*n
        for i in range(n-1,-1,-1):
            for j in range(32):
                if nums[i] & (1<<j):
                    last[j]=i
            ans[i]=max(1,max(last)-i+1)
        return ans

complexity

n time
n space

actually space is wrong its consatnt space cuz
ans array: n integers (this is output, usually not counted toward space complexity)