Watch 8 video solutions for Maximum OR, a medium level problem involving Array, Greedy, Bit Manipulation. This walkthrough by Prakhar Agrawal has 1,520 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |