Maximum OR solution and explanation
Infosys
7 more videos on this problem
Leetcode BiWeekly contest 104 - Medium - Maximum ORPrakhar Agrawal · 9:49 · 1K views
2680. Maximum OR || Biweekly contest 104 || leetcode || c++ in hindiCode Coder · 9:03 · 706 views
2680. Maximum OR || Leetcode Biweekly contest 104 || Medium is EASY || DPJeeetcode · 10:18 · 603 views
2680. Maximum OR (Leetcode Medium)Programming Live with Larry · 10:58 · 586 views
Maximum OR | Biweekly Contest 104codingMohan · 14:56 · 573 views
【每日一题】LeetCode 2680. Maximum ORHuifeng Guan · 12:21 · 363 views
[Eng] Leetcode | Weekly Contest 345 | 2680 Maximum ORCyCode · 12:00 · 142 views
Leetcode 2680 | Maximum OR | Bit Manipulation | Medium | Solution in C++Shekhar Gupta · 24:10 · 52 views
The problem
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 <= 15
Approach overview
Problem 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 1: Approach 1: Stack-Based Solution
This approach utilizes a stack data structure to effectively manage the elements, ensuring that operations can be performed efficiently.
def stack_based_solution(arr):
# Implementation of the stack approach goes hereimport java.util.Stack;
// Implementation of the stack approach goes here#include <iostream>
#include <stack>
// Implementation of the stack approach goes herefunction stackBasedSolution(arr) {
// Implementation of the stack approach goes here
}#include <stdio.h>
#include <stdlib.h>
// Implementation of the stack approach goes hereusing System;
using System.Collections.Generic;
// Implementation of the stack approach goes hereThis Python implementation...
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Approach 2: Two-Pointer Technique
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.
def two_pointer_technique(arr):
# Implementation of the two-pointer approach goes hereclass Solution {
// Implementation of the two-pointer approach goes here
}#include <iostream>
// Implementation of the two-pointer approach goes herefunction twoPointerTechnique(arr) {
// Implementation of the two-pointer approach goes here
}#include <stdio.h>
#include <stdlib.h>
// Implementation of the two-pointer approach goes hereusing System;
// Implementation of the two-pointer approach goes hereThis Python solution uses a two-pointer technique...
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Greedy + Preprocessing
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.
function maximumOr(nums: number[], k: number): number {
const n = nums.length;
const suf: bigint[] = Array(n + 1).fill(0n);
for (let i = n - 1; i >= 0; i--) {
suf[i] = suf[i + 1] | BigInt(nums[i]);
}
let [ans, pre] = [0, 0n];
for (let i = 0; i < n; i++) {
ans = Math.max(Number(ans), Number(pre | (BigInt(nums[i]) << BigInt(k)) | suf[i + 1]));
pre |= BigInt(nums[i]);
}
return ans;
}func maximumOr(nums []int, k int) int64 {
n := len(nums)
suf := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
suf[i] = suf[i+1] | nums[i]
}
ans, pre := 0, 0
for i, x := range nums {
ans = max(ans, pre|(nums[i]<<k)|suf[i+1])
pre |= x
}
return int64(ans)
}impl Solution {
pub fn maximum_or(nums: Vec<i32>, k: i32) -> i64 {
let n = nums.len();
let mut suf = vec![0; n + 1];
for i in (0..n).rev() {
suf[i] = suf[i + 1] | (nums[i] as i64);
}
let mut ans = 0i64;
let mut pre = 0i64;
let k64 = k as i64;
for i in 0..n {
ans = ans.max(pre | ((nums[i] as i64) << k64) | suf[i + 1]);
pre |= nums[i] as i64;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Stack-Based Solution | Time Complexity: O(n) |
| Approach 2: Two-Pointer Technique | Time Complexity: O(n) |
| Greedy + Preprocessing | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximum OR easy or hard?
Maximum OR is rated Medium. The challenge is recognizing that applying all k operations to one element maximizes the shifted bits and that prefix/suffix OR preprocessing reduces the evaluation from O(n^2) to O(n).
Maximum OR Python/Java solution
Most implementations compute suffix OR values, then iterate while maintaining a prefix OR. For each index, evaluate (nums[i] << k) combined with prefix and suffix contributions. The same logic translates directly across Python, Java, C++, and JavaScript.
How to solve Maximum OR in O(n)?
Precompute a suffix OR array where suffix[i] stores the OR of elements from i to the end. Iterate through the array while maintaining a running prefix OR. For each index, compute (nums[i] << k) | prefix | suffix[i+1] and track the maximum result.
What is the best approach for Maximum OR?
The optimal approach uses prefix and suffix OR arrays with a greedy observation. Apply all k doubling operations to a single element by computing nums[i] << k, then combine it with the OR of elements before and after that index. This allows evaluating every candidate in O(n) time.
Is Maximum OR asked at Google/Amazon/Meta?
Bit manipulation and prefix OR optimization problems similar to Maximum OR appear in interviews at companies like Amazon and Google. They test understanding of bit operations, greedy reasoning, and efficient array preprocessing.
What data structure is used in Maximum OR?
The solution mainly uses arrays for prefix and suffix OR storage. Some implementations also use stacks to track intermediate OR states, but the core technique relies on bitwise operations and linear array traversal.
What is the time complexity of Maximum OR?
The optimized solution runs in O(n) time with O(n) extra space for suffix OR storage. Each element is processed once to build prefix and suffix OR values, and evaluating the shifted candidate takes constant time.