You are given a 2D integer array grid of size m x n.

You must select exactly one integer from each row of the grid.

Return an integer denoting the minimum possible bitwise OR of the selected integers from each row.

In other words, you have a grid with m rows and n columns. From each of the m rows, you pick a single element. After picking one element per row, you compute the bitwise OR of all the chosen elements. Among all possible ways of selecting one element from each row, your task is to find the selection that produces the smallest possible bitwise OR value, and return that value.

For example, if the grid has rows [1, 6, 3], [4, 2, 9], and [7, 2, 8], you must pick exactly one number from each of the three rows, then OR them together. You want to choose the combination whose OR result is as small as possible.

Recall that the bitwise OR operation (|) sets a bit to 1 if that bit is 1 in any of the operands. Because OR can only turn bits on (never off), adding more numbers can only keep the result the same or make it larger. The challenge is to balance the choices across all rows so that the fewest high-value bits get set in the final combined result.

The key observation is that the bitwise OR operation can only turn bits on, never off. This means that once a bit appears in the result, it stays there no matter what else we OR. Since higher bits contribute much larger values than lower bits (a single high bit can outweigh all the lower bits combined), our top priority should always be to avoid setting the highest possible bits first.

This naturally leads to a greedy, bit-by-bit decision from the most significant bit down to the least significant bit. For each bit position, we ask: "Is it possible to construct a valid selection (one element per row) such that this bit, together with all the higher bits we've already committed to keeping as 0, stays 0?" If yes, we greedily keep this bit at 0, because doing so reduces the answer more than anything we could save on the lower bits later. If no, we are forced to accept this bit as 1 and move on.

To check whether a bit can stay 0, we track the bits we are trying to keep off. Let ans hold the bits we've already been forced to set to 1. When testing bit i, we form a mask = ans | ((1 << i) - 1). This mask represents all the bits we are allowed to have set: the bits already in ans, plus every bit below i (since we haven't decided those yet, we let them be free). The bits we're trying to keep 0 are exactly the ones not in this mask, which includes bit i and any higher bits we previously chose to keep 0.

Now for each row, we need at least one element x that doesn't violate this requirement — meaning x uses only the allowed bits, expressed as (x | mask) == mask. If every row can supply such an element, then bit i can safely remain 0, so we leave ans unchanged. But if any row has no valid element, then no matter how we pick, that bit (or a forbidden higher bit) must turn on, so we are forced to set bit i in ans with ans |= 1 << i.

By processing bits from high to low and locking in the smallest achievable value at each step, the greedy choices combine to give the globally minimum possible bitwise OR. The reason greedy works here is the dominance of higher bits: saving one high bit is always worth more than saving any combination of lower bits, so committing to the best high-bit decision first never causes us to miss a better overall answer.

The implementation uses a greedy bitwise construction pattern, building the answer one bit at a time from the most significant bit to the least significant. Below is a step-by-step walkthrough of how the code works.

Step 1: Determine how many bits we need to consider.

mx = max(map(max, grid))
m = mx.bit_length()

We first find the largest value mx across the entire grid using max(map(max, grid)). The number of bits we need to examine is mx.bit_length(), since no element in the grid can have a bit set beyond this position. This bounds the range of bit positions we iterate over.

Step 2: Initialize the answer.

ans = 0

We start with ans = 0, representing the optimistic assumption that we can keep every bit off. We will only set bits in ans when we are forced to.

Step 3: Iterate over bit positions from high to low.

for i in range(m - 1, -1, -1):
    mask = ans | ((1 << i) - 1)

For each bit position i (starting from the highest), we build a mask that represents the allowed bits:

• ans contributes the bits we have already been forced to set to 1.
• (1 << i) - 1 contributes all bits below position i, which we leave free since they are decided later.

The bits not in mask are the ones we are currently trying to keep 0 — namely bit i and any higher bits we previously committed to as 0.

Step 4: Check whether each row can satisfy the mask.

for row in grid:
    found = False
    for x in row:
        if (x | mask) == mask:
            found = True
            break
    if not found:
        ans |= 1 << i
        break

For every row, we look for at least one element x that uses only the allowed bits. The condition (x | mask) == mask is true exactly when x has no bits outside of mask, meaning picking x would not turn on bit i or any forbidden higher bit. As soon as we find such an element, we mark found = True and stop scanning that row.

If any row fails to provide a valid element (found stays False), it is impossible to keep bit i off, so we set it with ans |= 1 << i and break out early — there's no need to check the remaining rows for this bit since the decision is already made.

Step 5: Return the result.

return ans

After processing all bit positions, ans holds exactly the bits that had to be 1, which is the minimum possible bitwise OR.

Complexity Analysis

• Time complexity: O(B * m * n), where B is the number of bits (about 30 for typical integer ranges), and m * n is the total number of grid elements. For each of the B bit positions, we may scan every element of the grid.
• Space complexity: O(1), since we only use a constant number of integer variables (mx, m, ans, mask) regardless of input size.

Data structures and patterns used:

• Bit masking is the core technique, using mask to encode the set of allowed bits and the test (x | mask) == mask to verify feasibility.
• Greedy bit-by-bit decision making drives the algorithm: by resolving higher-value bits first and locking in the best choice at each step, the locally optimal decisions combine into the globally minimum OR.