LeetCode 3858 - Minimum Bitwise OR From Grid

We are given an m x n grid of positive integers. From each row, we must choose exactly one value. After making one choice per row, we compute the bitwise OR of all selected values. Our goal is to make that final OR value as small as possible.

leetcodemediumarraygreedybit-manipulationmatrix

LeetCode Problem 3858

Difficulty: 🟡 Medium
Topics: Array, Greedy, Bit Manipulation, Matrix

Solution

LeetCode 3858 - Minimum Bitwise OR From Grid

Problem Understanding

We are given an m x n grid of positive integers. From each row, we must choose exactly one value. After making one choice per row, we compute the bitwise OR of all selected values.

Our goal is to make that final OR value as small as possible.

In other words, if we choose:

  • one number from row 0
  • one number from row 1
  • ...
  • one number from row m - 1

and the chosen values are a₀, a₁, ..., aₘ₋₁, then we want to minimize:

$$a_0 ;|; a_1 ;|; \cdots ;|; a_{m-1}$$

The input size is large:

  • m * n <= 100000
  • each value is at most 100000

This immediately tells us that trying every possible combination is impossible. Even a modest grid could contain an enormous number of possible selections.

The most important observation is that the numbers themselves are small, at most 100000, which means only about 17 bits are relevant. This strongly suggests a bit manipulation solution.

Some important edge cases are:

  • A grid with only one row. We simply choose the smallest value whose OR is minimal.
  • Rows containing only large values with many bits set.
  • Situations where a particular bit cannot be eliminated because every candidate in some row contains that bit.
  • Situations where many bits can simultaneously be forced to zero.

The problem guarantees that every row contains at least one element, so a valid selection always exists.

Approaches

Brute Force

A direct approach would be to enumerate every possible selection.

For each row, choose one value, compute the OR of all chosen values, and keep track of the minimum result.

This is correct because it examines every possible combination.

However, if there are n choices per row and m rows, the number of combinations is:

$$n^m$$

which is astronomically large. Even very small inputs would become infeasible.

Key Observation

A bit in the final OR is 0 only if every selected number has that bit equal to 0.

Suppose we want to force some set of bits to be zero. Let those bits be represented by a mask forbidden.

For a row to participate in such a solution, it must contain at least one value whose set bits do not intersect with forbidden:

$$(value ,&, forbidden) = 0$$

If every row contains at least one such value, then we can select one valid value from each row and keep all bits in forbidden equal to zero in the final OR.

This gives us a feasibility test.

Since minimizing an integer means minimizing higher bits before lower bits, we can greedily process bits from most significant to least significant.

For each bit:

  • Try forcing it to zero.
  • Check whether all rows still have at least one valid candidate.
  • If yes, permanently forbid that bit.
  • Otherwise, that bit must remain 1 in the answer.

This is a classic bitwise greedy construction of the minimum possible result.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n^m) O(m) Tries every selection
Optimal O(B · m · n) O(1) Greedily determines each bit, where B ≈ 17

Since m * n ≤ 100000 and B = 17, the optimal approach is easily fast enough.

Algorithm Walkthrough

Step 1

Determine the relevant bit range.

Since:

$$grid[i][j] \le 100000$$

only bits 0 through 16 can appear.

Step 2

Maintain a mask called forbidden.

A bit set in forbidden represents a bit that we are attempting to keep equal to 0 in the final OR.

Initially:

forbidden = 0

Step 3

Process bits from most significant to least significant.

For each bit:

candidateForbidden = forbidden | (1 << bit)

This represents the assumption that the current bit can also be forced to zero.

Step 4

Check feasibility.

For every row, verify that at least one value satisfies:

(value & candidateForbidden) == 0

If a row has no such value, then the current set of forbidden bits is impossible.

Step 5

If every row has at least one valid value, permanently add this bit to forbidden.

Otherwise, the bit cannot be eliminated and therefore must be present in the final answer.

Step 6

Continue until all bits have been processed.

The bits that could not be forbidden form the minimum possible OR.

Why it works

The crucial property is that a bit is zero in the final OR if and only if every selected number has that bit equal to zero.

When we test a set of forbidden bits, we are checking whether each row still contains at least one candidate compatible with those restrictions. If every row does, then a valid selection exists.

Processing bits from highest to lowest is correct because minimizing an integer is equivalent to minimizing its most significant differing bit first. Whenever a bit can be forced to zero without making the problem impossible, doing so can only improve the answer. Therefore the greedy bit-by-bit construction produces the lexicographically smallest bit pattern, which is exactly the minimum possible OR.

Python Solution

from typing import List

class Solution:
    def minimumOR(self, grid: List[List[int]]) -> int:
        forbidden = 0
        answer = 0

        for bit in range(16, -1, -1):
            candidate_forbidden = forbidden | (1 << bit)

            feasible = True

            for row in grid:
                found = False

                for value in row:
                    if (value & candidate_forbidden) == 0:
                        found = True
                        break

                if not found:
                    feasible = False
                    break

            if feasible:
                forbidden = candidate_forbidden
            else:
                answer |= (1 << bit)

        return answer

Implementation Explanation

The variable forbidden stores the set of bits we have successfully forced to zero.

For each bit from 16 down to 0, we temporarily add that bit to the forbidden set and test whether every row still contains at least one compatible value.

The compatibility condition is:

(value & candidate_forbidden) == 0

which means the value contains none of the forbidden bits.

If every row has at least one compatible value, the restriction is achievable and we permanently add the bit to forbidden.

Otherwise, the bit must appear in the final OR, so we set that bit in answer.

After all bits are processed, answer contains exactly the bits that could not be eliminated.

Go Solution

func minimumOR(grid [][]int) int {
	forbidden := 0
	answer := 0

	for bit := 16; bit >= 0; bit-- {
		candidateForbidden := forbidden | (1 << bit)

		feasible := true

		for _, row := range grid {
			found := false

			for _, value := range row {
				if value&candidateForbidden == 0 {
					found = true
					break
				}
			}

			if !found {
				feasible = false
				break
			}
		}

		if feasible {
			forbidden = candidateForbidden
		} else {
			answer |= 1 << bit
		}
	}

	return answer
}

Go-Specific Notes

The Go implementation mirrors the Python solution almost exactly.

All values fit comfortably inside Go's int type because the largest possible answer is below 2^17.

Slices are used directly to iterate through rows and values, and no additional data structures are required.

Worked Examples

Example 1

grid = [[1,5],
        [2,4]]

Binary representations:

1 = 001
5 = 101
2 = 010
4 = 100

Consider the important bits.

Bit Can be forbidden? Reason
2 Yes Row 1 can use 1, Row 2 can use 2
1 No Second row would have no valid value
0 No Second row would have no valid value

Result:

answer = 011₂ = 3

Selection:

1 | 2 = 3

Example 2

grid = [[3,5],
        [6,4]]

Binary:

3 = 011
5 = 101
6 = 110
4 = 100

Process bits:

Bit Can be forbidden? Reason
2 No Every value in second row contains bit 2
1 Yes Choose 5 from row 1 and 4 from row 2
0 No Row 1 would have no valid value

Final answer:

101₂ = 5

Selection:

5 | 4 = 5

Example 3

grid = [[7,9,8]]

Binary:

7 = 0111
9 = 1001
8 = 1000

Single row case.

The smallest achievable OR is simply the minimum selectable value with respect to OR.

min(7, 9, 8) = 7

Result:

7

Complexity Analysis

Measure Complexity Explanation
Time O(B · m · n) For each bit, scan all grid elements
Space O(1) Only a few integer variables are used

Since B = 17 and m * n ≤ 100000, the running time is approximately:

17 × 100000 = 1.7 million operations

which is easily within limits.

Test Cases

sol = Solution()

assert sol.minimumOR([[1, 5], [2, 4]]) == 3      # Example 1
assert sol.minimumOR([[3, 5], [6, 4]]) == 5      # Example 2
assert sol.minimumOR([[7, 9, 8]]) == 7           # Example 3

assert sol.minimumOR([[1]]) == 1                 # Single cell
assert sol.minimumOR([[8, 1]]) == 1             # Single row, choose minimum OR

assert sol.minimumOR([[1], [2], [4]]) == 7      # Forced choices

assert sol.minimumOR([[1, 2], [4, 8]]) == 5     # Choose 1 and 4

assert sol.minimumOR([[7, 7], [7, 7]]) == 7     # All values identical

assert sol.minimumOR([[1, 3], [2, 3]]) == 3     # Cannot eliminate both bits

assert sol.minimumOR([[16, 1], [16, 2], [16, 4]]) == 7  # Avoid high bit

assert sol.minimumOR([[31], [31], [31]]) == 31  # Maximum overlap

assert sol.minimumOR([[5, 1], [6, 2], [4, 8]]) == 5     # Mixed choices

Test Summary

Test Why
[[1,5],[2,4]] Official example 1
[[3,5],[6,4]] Official example 2
[[7,9,8]] Official example 3
[[1]] Smallest possible input
[[8,1]] Single row behavior
[[1],[2],[4]] All choices forced
[[1,2],[4,8]] Multiple valid selections
[[7,7],[7,7]] Repeated values
[[1,3],[2,3]] Some bits unavoidable
[[16,1],[16,2],[16,4]] Greedy elimination of high bit
[[31],[31],[31]] Maximum overlap of bits
[[5,1],[6,2],[4,8]] General mixed case

Edge Cases

Single Row Grid

When there is only one row, the final OR is simply the chosen value itself. The algorithm naturally handles this because feasibility depends only on finding a valid value in that single row. The greedy process effectively identifies the smallest achievable value.

Bits Present in Every Candidate of a Row

Suppose every value in some row contains a particular bit. Since one value from that row must always be selected, that bit can never be eliminated from the final OR. During the feasibility check, the algorithm detects that no candidate remains valid once that bit is forbidden, so the bit is correctly forced into the answer.

High Bits That Can Be Avoided

A common source of mistakes is assuming that a bit appearing frequently must be present in the final answer. In reality, if every row contains at least one alternative value without that bit, the bit can be eliminated entirely. The feasibility test checks rows independently and therefore correctly identifies when a high bit can be avoided by choosing different values.

Rows with Only One Element

If a row contains exactly one value, that value is effectively mandatory. The algorithm still works because the feasibility check simply evaluates whether that lone value satisfies the current forbidden-bit constraints. If it does not, the corresponding bit is forced into the answer.