Smallest Subarrays With Maximum Bitwise Or - Leetcode Solution

Problem statement:

Given an array of integers nums, return the length of the smallest subarray with the maximum bitwise OR value.

Solution:

One way to solve this problem is to use a sliding window approach. We start with a window of size 1 and keep expanding it until we have a maximum bitwise OR value. Then we shrink the window from the left until the value decreases. We repeat this process until we have traversed the whole array. The length of the smallest window with the maximum bitwise OR value is our answer.

Algorithm:

1. Initialize a variable max_bitwise_OR to 0.
2. Initialize a variable min_length to the length of the array.
3. Initialize two pointers, left and right, both pointing to the first element of the array.
4. While the right pointer is less than the length of the array, do the following: a. Calculate the bitwise OR of all the elements in the current window (from left to right). b. If the bitwise OR value is greater than the current max_bitwise_OR, update max_bitwise_OR to this value. c. If the bitwise OR value is equal to the current max_bitwise_OR, update min_length to the minimum of its current value and the length of the current window. d. Increment the right pointer. e. If the bitwise OR value is less than the current max_bitwise_OR, increment the left pointer.
5. Return min_length.

Code:

The code for the above algorithm is as follows:

class Solution:
    def findLength(self, nums: List[int]) -> int:
        max_bitwise_OR = 0
        min_length = len(nums)
        left = 0
        right = 0
        
        while right < len(nums):
            bitwise_OR = 0
            for i in range(left, right+1):
                bitwise_OR |= nums[i]
                
            if bitwise_OR > max_bitwise_OR:
                max_bitwise_OR = bitwise_OR
                min_length = right - left + 1
            elif bitwise_OR == max_bitwise_OR:
                min_length = min(min_length, right - left + 1)
                
            if bitwise_OR < max_bitwise_OR:
                left += 1
            else:
                right += 1
        
        return min_length

Time Complexity:

The time complexity of this solution is O(n^2) in the worst case, where n is the length of the array. This is because we are calculating the bitwise OR value of all the elements in each window. However, in practice, the actual time complexity will be much less than this because the window size will not be very large most of the time.

Space Complexity:

The space complexity of this solution is O(1) because we are not using any extra space apart from a few variables.

1