Is Minimum Bitwise OR From Grid easy or hard?

The problem is rated Medium because it combines grid traversal with bitwise reasoning. Recognizing that OR results can be optimized bit by bit is the key insight. Once that observation is made, the implementation becomes a series of BFS checks.

Minimum Bitwise OR From Grid Python/Java solution

Implement the greedy bit filtering approach: iterate bits from high to low, block cells containing that bit, and run BFS to check reachability. If the destination becomes unreachable, add that bit to the answer and allow those cells again. The same logic translates cleanly to Python, Java, C++, Go, and TypeScript.

How to solve Minimum Bitwise OR From Grid in O(n)?

The problem cannot be solved in strict O(n) for a grid because every cell may need to be inspected. The practical optimal solution is O(32*m*n), where each bit is tested with a BFS reachability check. This is effectively linear in the grid size with a small constant factor.

What is the best approach for Minimum Bitwise OR From Grid?

The most efficient method uses greedy bit filtering combined with BFS/DFS. Iterate bits from the most significant to the least significant and attempt to forbid cells containing that bit. If a path from the top-left to bottom-right still exists, the bit stays 0; otherwise it must be included in the answer. This runs in O(32*m*n) time and O(m*n) space.

Is Minimum Bitwise OR From Grid asked at Google/Amazon/Meta?

Bit manipulation combined with graph traversal appears frequently in interviews at companies like Google, Amazon, and Meta. Variants that minimize XOR/OR cost along a path or require bitwise optimization over grids are common in coding rounds.

What data structure is used in Minimum Bitwise OR From Grid?

The solution typically uses a queue for BFS traversal along with a visited matrix to track explored cells. If using the alternative shortest-path method, a priority queue (min-heap) is used to implement Dijkstra's algorithm with OR-based costs.

What is the time complexity of Minimum Bitwise OR From Grid?

The optimal greedy approach runs in O(32 * m * n) time because each of the 32 bits is tested with a grid traversal. Space complexity is O(m*n) for the visited matrix during BFS. A Dijkstra-based alternative runs in O(m*n log(m*n)) time with a priority queue.

Description Hints 3 Solution Video 18:40

3858. Minimum Bitwise OR From Grid

Medium27.5% acceptance1 company

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.

Example 1:

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

Output: 3

Explanation:

Choose 1 from the first row and 2 from the second row.
The bitwise OR of 1 | 2 = 3, which is the minimum possible.

Example 2:

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

Output: 5

Explanation:

Choose 5 from the first row and 4 from the second row.
The bitwise OR of 5 | 4 = 5, which is the minimum possible.

Example 3:

Input: grid = [[7,9,8]]

Output: 7

Explanation:

Choosing 7 gives the minimum bitwise OR.

Constraints:

1 <= m == grid.length <= 10⁵
1 <= n == grid[i].length <= 10⁵
m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Solve greedily, bit by bit from the most significant to the least significant

Hint 2

For a bit, check whether it is possible to exclude it from the OR by choosing, in every row, at least one number with that bit unset

Hint 3

Accumulate all bits that cannot be excluded; the final value is the minimum possible bitwise OR

18:40

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minimumOR(self, grid: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[1,5],[2,4]]

Input

[[3,5],[6,4]]

Input

[[7,9,8]]

Your code is saved on this device.Solution