You are given a 0-indexed integer array nums of length n and an integer k. In an operation, you can choose an element and multiply it by 2.
Return the maximum possible value of nums[0] | nums[1] | ... | nums[n - 1] that can be obtained after applying the operation on nums at most k times.
Note that a | b denotes the bitwise or between two integers a and b.
Example 1:
Input: nums = [12,9], k = 1 Output: 30 Explanation: If we apply the operation to index 1, our new array nums will be equal to [12,18]. Thus, we return the bitwise or of 12 and 18, which is 30.
Example 2:
Input: nums = [8,1,2], k = 2 Output: 35 Explanation: If we apply the operation twice on index 0, we yield a new array of [32,1,2]. Thus, we return 32|1|2 = 35.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 15Problem Overview: You get an integer array nums and an integer k. Each operation doubles a chosen element (multiplying by 2). After performing k operations, compute the maximum possible bitwise OR of the array. The key observation: doubling shifts bits left, so concentrating all operations on one element usually maximizes the final OR.
Approach 1: Stack-Based Solution (O(n) time, O(n) space)
This approach processes the array while maintaining a stack of prefix OR values. As you iterate through nums, the stack stores cumulative OR results of previous elements. For each index i, temporarily apply all k operations by computing nums[i] << k. Combine it with the OR of the remaining elements tracked through the stack and precomputed suffix values. The stack helps preserve intermediate OR states without recomputing from scratch, making each element evaluation constant time. This approach works well when you want structured tracking of prefix contributions during iteration.
Approach 2: Two-Pointer Technique (O(n) time, O(n) space)
The optimal solution relies on prefix and suffix OR arrays. First compute a suffix OR array where suffix[i] stores the OR of elements from i to the end. Then iterate from left to right using a pointer while maintaining a running prefix OR. For each index i, simulate applying all k operations to that element: (nums[i] << k). Combine three parts: prefix OR of elements before i, the shifted value, and suffix OR after i. Update the maximum result. This works because OR is associative and you can evaluate the impact of boosting each element independently. The technique uses linear scans from both ends and avoids nested iteration.
Recommended for interviews: The two-pointer prefix/suffix OR approach is the expected solution. It demonstrates understanding of bit manipulation, efficient array traversal, and greedy reasoning. A brute-force recomputation of OR for every candidate would be O(n^2), so showing the O(n) prefix optimization signals strong familiarity with patterns similar to prefix sum and array preprocessing.
This approach utilizes a stack data structure to effectively manage the elements, ensuring that operations can be performed efficiently.
This C implementation uses a stack to...
Time Complexity: O(n)
Space Complexity: O(n)
This technique leverages two pointers to traverse the data structure from both the beginning and end, allowing for optimal use of the array's properties.
This C implementation employs two pointers to...
Time Complexity: O(n)
Space Complexity: O(1)
We notice that in order to maximize the answer, we should apply k times of bitwise OR to the same number.
First, we preprocess the suffix OR value array suf of the array nums, where suf[i] represents the bitwise OR value of nums[i], nums[i + 1], cdots, nums[n - 1].
Next, we traverse the array nums from left to right, and maintain the current prefix OR value pre. For the current position i, we perform k times of bitwise left shift on nums[i], i.e., nums[i] times 2^k, and perform bitwise OR operation with pre to obtain the intermediate result. Then, we perform bitwise OR operation with suf[i + 1] to obtain the maximum OR value with nums[i] as the last number. By enumerating all possible positions i, we can obtain the final answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Approach 1: Stack-Based Solution | Time Complexity: O(n) |
| Approach 2: Two-Pointer Technique | Time Complexity: O(n) |
| Greedy + Preprocessing | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based OR Tracking | O(n) | O(n) | When maintaining prefix OR states during iteration to avoid recomputation |
| Two-Pointer Prefix/Suffix OR | O(n) | O(n) | Best general solution; evaluates each index using prefix and suffix OR arrays |
Leetcode BiWeekly contest 104 - Medium - Maximum OR • Prakhar Agrawal • 1,520 views views
Watch 7 more video solutions →Practice Maximum OR with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor