LeetCode 2680 - Maximum OR

In this problem, we are given an integer array nums and an integer k. We may perform at most k operations, where each operation selects one element and multiplies it by 2. Multiplying by 2 in binary is equivalent to shifting all bits one position to the left.

leetcodemediumarraygreedybit-manipulationprefix-sum

LeetCode Problem 2680

Difficulty: 🟡 Medium
Topics: Array, Greedy, Bit Manipulation, Prefix Sum

Solution

Problem Understanding

In this problem, we are given an integer array nums and an integer k. We may perform at most k operations, where each operation selects one element and multiplies it by 2.

Multiplying by 2 in binary is equivalent to shifting all bits one position to the left. For example:

  • 5 in binary is 101
  • 5 * 2 = 10, which is 1010

After performing up to k operations, we must compute the bitwise OR of all array elements and return the maximum possible value.

The expression:

nums[0] | nums[1] | ... | nums[n - 1]

combines all bits that are set in any element. A bit in the final result becomes 1 if at least one number contains that bit.

The key challenge is deciding where to spend the k doubling operations. We can distribute operations across multiple elements, or apply all operations to a single element.

The constraints are important:

  • n can be as large as 10^5
  • nums[i] can be up to 10^9
  • k is at most 15

The large array size means we need an algorithm close to linear time. A quadratic solution would be too slow.

An important observation is that left shifting one element by k positions can create very large higher bits, often contributing more to the final OR than distributing shifts across many numbers.

Several edge cases are worth considering:

  • Arrays with only one element
  • Very large values already containing many high bits
  • Cases where shifting a smaller number creates a more useful high bit
  • Situations where applying all operations to one number is optimal
  • Arrays where multiple numbers already overlap heavily in binary representation

The problem guarantees:

  • The array is non-empty
  • Every value is positive
  • k >= 1

This avoids complications involving empty arrays or negative integers.

Approaches

Brute Force Approach

A brute force strategy would try every possible way to distribute the k operations among the array elements.

For example, if k = 3, we could try:

  • All 3 operations on index 0
  • Two on index 0, one on index 1
  • One on each of three indices
  • Many other combinations

For each distribution, we would:

  1. Apply the shifts
  2. Compute the final OR
  3. Track the maximum

This approach is correct because it explores every possible valid state.

However, it is computationally infeasible. The number of ways to distribute k operations among n elements grows combinatorially. Even though k <= 15, n can reach 10^5, making exhaustive search impossible.

Key Insight

The crucial observation is that the OR operation benefits most from creating new higher-order bits.

Applying multiple left shifts to the same number creates exponentially larger values because:

x * 2^k

adds bits farther to the left.

If we split operations among multiple elements, we usually create overlapping lower bits instead of introducing entirely new higher bits.

This leads to the optimal insight:

We only need to consider applying all k operations to exactly one element.

For every index i:

  1. Shift nums[i] left by k
  2. OR it with all other unchanged elements
  3. Compute the resulting value

The remaining challenge is computing the OR of all elements except index i efficiently.

We solve this using prefix OR and suffix OR arrays.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Tries every distribution of operations
Optimal O(n) O(n) Uses prefix and suffix OR arrays

Algorithm Walkthrough

Step 1: Build a Prefix OR Array

Create an array prefix where:

prefix[i]

stores the OR of all elements from index 0 through i.

Example:

nums = [8,1,2]

prefix[0] = 8
prefix[1] = 8 | 1 = 9
prefix[2] = 9 | 2 = 11

This allows us to quickly retrieve the OR of elements before any index.

Step 2: Build a Suffix OR Array

Create another array suffix where:

suffix[i]

stores the OR of all elements from index i through n - 1.

Example:

suffix[2] = 2
suffix[1] = 1 | 2 = 3
suffix[0] = 8 | 3 = 11

This lets us efficiently retrieve the OR of elements after any index.

Step 3: Try Each Element as the Shifted Element

For each index i:

  1. Compute the OR of all elements before i
  2. Compute the OR of all elements after i
  3. Shift nums[i] left by k
  4. OR everything together

The candidate value becomes:

left_or | (nums[i] << k) | right_or

Step 4: Track the Maximum Result

Keep a running maximum across all candidates.

Since every index is evaluated independently, we eventually find the optimal answer.

Why it works

The correctness relies on the fact that left shifting increases the magnitude of bits exponentially. High-order bits dominate the OR result much more than repeatedly setting already existing lower bits.

Because OR only cares whether a bit is present at least once, concentrating all shifts on one element maximizes the chance of introducing new higher bits. Prefix and suffix OR arrays ensure we can efficiently combine the shifted element with the rest of the array.

Python Solution

from typing import List

class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        n = len(nums)

        prefix = [0] * n
        suffix = [0] * n

        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] | nums[i]

        suffix[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i + 1] | nums[i]

        answer = 0

        for i in range(n):
            left_or = prefix[i - 1] if i > 0 else 0
            right_or = suffix[i + 1] if i < n - 1 else 0

            shifted_value = nums[i] << k

            candidate = left_or | shifted_value | right_or

            answer = max(answer, candidate)

        return answer

The implementation begins by constructing the prefix OR array. Each entry accumulates the OR of all previous elements including the current one.

Next, the suffix OR array is built in reverse order. This allows constant-time access to the OR of elements to the right of any position.

The main loop evaluates each index as the element receiving all k operations. The shifted value is computed using:

nums[i] << k

which is equivalent to multiplying by 2^k.

For each position, we combine:

  • OR of all elements before the index
  • Shifted current element
  • OR of all elements after the index

The maximum candidate is returned at the end.

Go Solution

func maximumOr(nums []int, k int) int64 {
	n := len(nums)

	prefix := make([]int64, n)
	suffix := make([]int64, n)

	prefix[0] = int64(nums[0])
	for i := 1; i < n; i++ {
		prefix[i] = prefix[i-1] | int64(nums[i])
	}

	suffix[n-1] = int64(nums[n-1])
	for i := n - 2; i >= 0; i-- {
		suffix[i] = suffix[i+1] | int64(nums[i])
	}

	var answer int64 = 0

	for i := 0; i < n; i++ {
		var leftOr int64 = 0
		var rightOr int64 = 0

		if i > 0 {
			leftOr = prefix[i-1]
		}

		if i < n-1 {
			rightOr = suffix[i+1]
		}

		shiftedValue := int64(nums[i]) << k

		candidate := leftOr | shiftedValue | rightOr

		if candidate > answer {
			answer = candidate
		}
	}

	return answer
}

The Go implementation closely mirrors the Python version.

One important difference is the use of int64. Since shifting values left by up to 15 positions can exceed the range of a 32-bit integer, we explicitly use int64 to avoid overflow.

Slices are used for the prefix and suffix arrays, and bitwise operations behave similarly to Python.

Worked Examples

Example 1

nums = [12,9]
k = 1

Binary representations:

12 = 1100
9  = 1001

Prefix OR

Index Value Prefix OR
0 12 12
1 9 13

Because:

1100 | 1001 = 1101 = 13

Suffix OR

Index Value Suffix OR
1 9 9
0 12 13

Try shifting each element

Shifted Index Shifted Value Result
0 24 24 | 9 = 25
1 18 12 | 18 = 30

Maximum result:

30

Example 2

nums = [8,1,2]
k = 2

Binary:

8 = 1000
1 = 0001
2 = 0010

Prefix OR

Index Prefix OR
0 8
1 9
2 11

Suffix OR

Index Suffix OR
2 2
1 3
0 11

Evaluate each index

Index Shifted Value Candidate
0 32 32 | 1 | 2 = 35
1 4 8 | 4 | 2 = 14
2 8 8 | 1 | 8 = 9

Maximum:

35

Complexity Analysis

Measure Complexity Explanation
Time O(n) Prefix construction, suffix construction, and evaluation each scan the array once
Space O(n) Prefix and suffix arrays each require linear storage

The algorithm performs only a constant number of passes through the array. Every OR operation is constant time because integers have bounded size. This makes the solution efficient enough for n = 10^5.

Test Cases

from typing import List

class Solution:
    def maximumOr(self, nums: List[int], k: int) -> int:
        n = len(nums)

        prefix = [0] * n
        suffix = [0] * n

        prefix[0] = nums[0]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] | nums[i]

        suffix[n - 1] = nums[n - 1]
        for i in range(n - 2, -1, -1):
            suffix[i] = suffix[i + 1] | nums[i]

        answer = 0

        for i in range(n):
            left_or = prefix[i - 1] if i > 0 else 0
            right_or = suffix[i + 1] if i < n - 1 else 0

            candidate = left_or | (nums[i] << k) | right_or

            answer = max(answer, candidate)

        return answer

solution = Solution()

assert solution.maximumOr([12, 9], 1) == 30  # provided example 1
assert solution.maximumOr([8, 1, 2], 2) == 35  # provided example 2

assert solution.maximumOr([1], 1) == 2  # single element
assert solution.maximumOr([1], 5) == 32  # large shift on single value

assert solution.maximumOr([1, 2, 4], 1) == 12  # shifting largest element
assert solution.maximumOr([7, 7, 7], 3) == 63  # overlapping bits

assert solution.maximumOr([1, 1, 1], 15) == 32769  # maximum shift
assert solution.maximumOr([1024, 512], 2) == 4608  # larger values

assert solution.maximumOr([3, 2, 4], 2) == 19  # middle element not optimal
assert solution.maximumOr([5, 1, 1], 3) == 41  # concentrating shifts

assert solution.maximumOr([9, 8, 3, 5], 4) == 159  # multiple candidates

Test Summary

Test Why
[12,9], k=1 Validates provided example
[8,1,2], k=2 Validates provided example
[1], k=1 Smallest possible array
[1], k=5 Large shift on single element
[1,2,4], k=1 Confirms largest element may be optimal
[7,7,7], k=3 Handles repeated overlapping bits
[1,1,1], k=15 Stress test for maximum shift
[1024,512], k=2 Tests larger binary values
[3,2,4], k=2 Ensures algorithm checks every index
[5,1,1], k=3 Demonstrates concentrated shifts
[9,8,3,5], k=4 General multi-element scenario

Edge Cases

One important edge case is an array containing only a single element. In this situation, there are no other elements contributing to the OR value, so the answer is simply that element shifted left by k. The implementation handles this naturally because both left_or and right_or become 0.

Another tricky case occurs when many elements already share the same set bits. For example:

[7,7,7]

Since OR ignores duplicate bits, distributing operations across multiple elements adds little value. The implementation correctly identifies that shifting one element as much as possible produces the best higher-order bits.

A third important edge case involves very large shifts. Since k can reach 15, left shifting may produce values larger than 32-bit integer limits. Python handles arbitrarily large integers automatically, but the Go solution explicitly uses int64 to prevent overflow.

A final subtle case is when the largest numerical element is not necessarily the best candidate to shift. Sometimes a smaller value produces more beneficial new bits after shifting. Because the algorithm evaluates every index independently, it never assumes the largest current value is automatically optimal.