Skip to main content
Talentd

Maximum OR - Solution & Explanation

MediumArrayGreedyBit ManipulationPrefix Sum12 min readAsked at: Microsoft, Visa, Infosys +2
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= 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.

This C implementation uses a stack to...

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

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.

This C implementation employs two pointers to...

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Stack-Based Solution

Time Complexity: O(n)
Space Complexity: O(n)

Approach 2: Two-Pointer Technique

Time Complexity: O(n)
Space Complexity: O(1)

Greedy + Preprocessing—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-Based OR TrackingO(n)O(n)When maintaining prefix OR states during iteration to avoid recomputation
Two-Pointer Prefix/Suffix ORO(n)O(n)Best general solution; evaluates each index using prefix and suffix OR arrays

Video Solution

Leetcode BiWeekly contest 104 - Medium - Maximum OR • Prakhar Agrawal • 1,557 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Maximum OR with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays