Skip to content

2411. Smallest Subarrays With Maximum Bitwise OR 👍

  • Time: $O(30n) = O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  vector<int> smallestSubarrays(vector<int>& nums) {
    constexpr int kMaxBit = 30;
    vector<int> ans(nums.size(), 1);
    // closest[j] := the closest index i s.t. the j-th bit of nums[i] is 1
    vector<int> closest(kMaxBit);

    for (int i = nums.size() - 1; i >= 0; --i)
      for (int j = 0; j < kMaxBit; ++j) {
        if (nums[i] >> j & 1)
          closest[j] = i;
        ans[i] = max(ans[i], closest[j] - i + 1);
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int[] smallestSubarrays(int[] nums) {
    final int kMaxBit = 30;
    int[] ans = new int[nums.length];
    // closest[j] := the closest index i s.t. the j-th bit of nums[i] is 1
    int[] closest = new int[kMaxBit];

    Arrays.fill(ans, 1);

    for (int i = nums.length - 1; i >= 0; --i)
      for (int j = 0; j < kMaxBit; ++j) {
        if ((nums[i] >> j & 1) == 1)
          closest[j] = i;
        ans[i] = Math.max(ans[i], closest[j] - i + 1);
      }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def smallestSubarrays(self, nums: list[int]) -> list[int]:
    kMaxBit = 30
    ans = [1] * len(nums)
    # closest[j] := the closest index i s.t. the j-th bit of nums[i] is 1
    closest = [0] * kMaxBit

    for i in reversed(range(len(nums))):
      for j in range(kMaxBit):
        if nums[i] >> j & 1:
          closest[j] = i
        ans[i] = max(ans[i], closest[j] - i + 1)

    return ans