LeetCode 2411: Smallest Subarrays With Maximum Bitwise OR Solution

Master LeetCode problem 2411 (Smallest Subarrays With Maximum Bitwise OR), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2411. Smallest Subarrays With Maximum Bitwise OR

Medium

Array Binary Search Bit Manipulation Sliding Window

Problem Explanation

Explanation

To solve this problem, we can iterate over the input array and maintain a sliding window. We will keep track of the maximum value encountered so far and its position. For each index, we will determine the smallest subarray starting at that index that produces the maximum bitwise OR. We will use a deque to store the indices of elements in decreasing order of their values.

Initialize an empty deque and an answer array of size n.
Iterate over the array nums.
For each index i, remove indices from the front of the deque that are not relevant anymore (out of the sliding window or smaller values).
While the deque is not empty and the current element is greater than the element at the back of the deque, remove the back element.
Add the current index to the back of the deque.
Calculate the minimum subarray length for the maximum OR based on the current element and the element at the front of the deque.
Update the answer array with this minimum length.
Repeat steps 2-7 for all indices.
Return the answer array.

Time Complexity: O(n) where n is the number of elements in the input array nums. Space Complexity: O(n) for the deque and answer array.

Solution Code

class Solution {
    public int[] minSubarray(int[] nums) {
        int n = nums.length;
        Deque<Integer> deque = new ArrayDeque<>();
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);

            while (deque.peekFirst() < i - answer[i]) {
                deque.pollFirst();
            }

            answer[i] = i - deque.peekFirst() + 1;
        }

        return answer;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2411 (Smallest Subarrays With Maximum Bitwise OR)?

This page provides optimized solutions for LeetCode problem 2411 (Smallest Subarrays With Maximum Bitwise OR) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2411 (Smallest Subarrays With Maximum Bitwise OR)?

The time complexity for LeetCode 2411 (Smallest Subarrays With Maximum Bitwise OR) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2411 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2411 in Java, C++, or Python.

Back to LeetCode Solutions