Minimum Bitwise OR From Grid - Solution & Explanation

Problem Overview: You are given an m x n grid where each cell contains an integer. Starting from the top-left cell, reach the bottom-right cell while minimizing the bitwise OR of all values along the chosen path. Movement is typically restricted to valid adjacent cells in the matrix. The challenge is that once a bit becomes 1 in the OR result, it cannot be reverted.

Approach 1: Dijkstra with Bitwise OR State (O(m*n log(m*n)) time, O(m*n) space)

Treat the grid as a weighted graph. Each move to a neighboring cell produces a new cost equal to current_cost | grid[nr][nc]. Use a priority queue similar to Dijkstra's algorithm to always expand the state with the smallest OR value so far. Maintain a distance matrix storing the smallest OR seen for each cell and skip states that produce larger values. This approach works because the OR operation is monotonic: costs never decrease as you extend the path.

The method is straightforward and reliable for moderate grid sizes. It resembles classic shortest path problems and uses common structures like priority queues and distance arrays.

Approach 2: Greedy Bit Filtering + BFS (O(32 * m * n) time, O(m*n) space)

The optimal approach leverages bit manipulation and a greedy observation. The OR result is determined bit by bit. Higher bits contribute more to the final value, so attempt to keep them 0 whenever possible.

Iterate bits from the most significant (for example 31) down to 0. For each bit, temporarily forbid stepping on cells whose value contains that bit (grid[i][j] & (1 << bit)). Run a BFS/DFS to check if the bottom-right cell is still reachable. If a path exists, that bit can remain 0 in the final answer. If no path exists, the bit is unavoidable, so add it to the result and allow those cells again.

This works because the OR operation accumulates bits irreversibly. Deciding higher bits first ensures the smallest possible final integer. The reachability check is simply a grid traversal using techniques from matrix problems and greedy algorithms.

Recommended for interviews: The greedy bit-by-bit filtering approach is what most interviewers expect. It shows understanding of how bitwise OR behaves and reduces the search space to at most 32 reachability checks. Mentioning the Dijkstra formulation first demonstrates baseline graph thinking, while implementing the greedy method shows stronger optimization skills.