You are given a 0-indexed array nums of length n, consisting of non-negative integers. For each index i from 0 to n - 1, you must determine the size of the minimum sized non-empty subarray of nums starting at i (inclusive) that has the maximum possible bitwise OR.
Bij be the bitwise OR of the subarray nums[i...j]. You need to find the smallest subarray starting at i, such that bitwise OR of this subarray is equal to max(Bik) where i <= k <= n - 1.The bitwise OR of an array is the bitwise OR of all the numbers in it.
Return an integer array answer of size n where answer[i] is the length of the minimum sized subarray starting at i with maximum bitwise OR.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,0,2,1,3] Output: [3,3,2,2,1] Explanation: The maximum possible bitwise OR starting at any index is 3. - Starting at index 0, the shortest subarray that yields it is [1,0,2]. - Starting at index 1, the shortest subarray that yields the maximum bitwise OR is [0,2,1]. - Starting at index 2, the shortest subarray that yields the maximum bitwise OR is [2,1]. - Starting at index 3, the shortest subarray that yields the maximum bitwise OR is [1,3]. - Starting at index 4, the shortest subarray that yields the maximum bitwise OR is [3]. Therefore, we return [3,3,2,2,1].
Example 2:
Input: nums = [1,2] Output: [2,1] Explanation: Starting at index 0, the shortest subarray that yields the maximum bitwise OR is of length 2. Starting at index 1, the shortest subarray that yields the maximum bitwise OR is of length 1. Therefore, we return [2,1].
Constraints:
n == nums.length1 <= n <= 1050 <= nums[i] <= 109The brute force approach involves checking all possible combinations or permutations to find the desired solution. This approach is generally easy to implement but may not be efficient for large inputs due to its high computational complexity.
This C code iterates over every pair of elements in the array using nested loops, allowing you to perform the desired operation on each pair.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N^2)
Space Complexity: O(1)
This approach utilizes a hash map to store and quickly access elements based on certain conditions defined by the problem. It significantly helps in reducing the computation time by eliminating unnecessary iterations.
This C code uses a hash table to keep track of element occurrences, allowing for efficient duplicate detection or fulfilling other conditions in O(1) time per operation.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N)
Space Complexity: O(N)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(N^2) |
| Optimized Approach with Hashing | Time Complexity: O(N) |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,241 views views
Watch 9 more video solutions →Practice Smallest Subarrays With Maximum Bitwise OR with our built-in code editor and test cases.
Practice on FleetCode