Minimum Bitwise OR From Grid solution and explanation
Google
7 more videos on this problem
Leetcode 3858 | Minimum Bitwise OR From Grid | Leetcode weekly contest 491CodeWithMeGuys · 18:40 · 1K views
LeetCode Problem 3858 | Minimum Bitwise OR From GridRepovive TV · 13:38 · 713 views
3858. Minimum Bitwise OR From Grid (Leetcode Medium)Programming Live with Larry · 23:37 · 462 views
3858. Minimum Bitwise OR From Grid|leetcode 3858 |Minimum Bitwise OR From Grid|leetcode contest 491Code Thoughts · 14:27 · 426 views
Minimum Bitwise OR From Grid | LeetCode 3858 | Weekly Contest 491 | Java | Developer CoderDeveloper Coder · 26:51 · 419 views
LeetCode Weekly Contest 491 Q3. LeetCode 3858 Minimum Bitwise OR From GridUnbound Coder · 8:39 · 233 views
LeetCode 3858 | Minimum Bitwise OR From Grid | Binary Search | JavaCode Kage · 7:26 · 172 views
Leetcode 3858 | Minimum Bitwise OR From Grid | Weekly Contest 491Code Like Him · 3:52 · 55 views
The problem
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 <= 1051 <= n == grid[i].length <= 105m * n <= 1051 <= grid[i][j] <= 105
Approach overview
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.
Solution
class Solution:
def minimumOR(self, grid: List[List[int]]) -> int:
mx = max(map(max, grid))
m = mx.bit_length()
ans = 0
for i in range(m - 1, -1, -1):
mask = ans | ((1 << i) - 1)
for row in grid:
found = False
for x in row:
if (x | mask) == mask:
found = True
break
if not found:
ans |= 1 << i
break
return ansclass Solution {
public int minimumOR(int[][] grid) {
int mx = 0;
for (int[] row : grid) {
for (int x : row) {
mx = Math.max(mx, x);
}
}
int m = 32 - Integer.numberOfLeadingZeros(mx);
int ans = 0;
for (int i = m - 1; i >= 0; i--) {
int mask = ans | ((1 << i) - 1);
for (int[] row : grid) {
boolean found = false;
for (int x : row) {
if ((x | mask) == mask) {
found = true;
break;
}
}
if (!found) {
ans |= 1 << i;
break;
}
}
}
return ans;
}
}class Solution {
public:
int minimumOR(vector<vector<int>>& grid) {
int mx = 0;
for (auto& row : grid) {
mx = max(mx, ranges::max(row));
}
int m = 32 - __builtin_clz(mx);
int ans = 0;
for (int i = m - 1; i >= 0; i--) {
int mask = ans | ((1 << i) - 1);
for (auto& row : grid) {
bool found = false;
for (int x : row) {
if ((x | mask) == mask) {
found = true;
break;
}
}
if (!found) {
ans |= 1 << i;
break;
}
}
}
return ans;
}
};function minimumOR(grid: number[][]): number {
let mx = 0;
for (const row of grid) {
mx = Math.max(mx, Math.max(...row));
}
const m = mx === 0 ? 0 : 32 - Math.clz32(mx);
let ans = 0;
for (let i = m - 1; i >= 0; i--) {
const mask = ans | ((1 << i) - 1);
for (const row of grid) {
let found = false;
for (const x of row) {
if ((x | mask) === mask) {
found = true;
break;
}
}
if (!found) {
ans |= 1 << i;
break;
}
}
}
return ans;
}func minimumOR(grid [][]int) int {
mx := 0
for _, row := range grid {
mx = max(mx, slices.Max(row))
}
m := bits.Len(uint(mx))
ans := 0
for i := m - 1; i >= 0; i-- {
mask := ans | ((1 << i) - 1)
for _, row := range grid {
found := false
for _, x := range row {
if (x | mask) == mask {
found = true
break
}
}
if !found {
ans |= 1 << i
break
}
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra with Bitwise OR Cost | O(m*n log(m*n)) | O(m*n) | General graph interpretation of the grid; easiest to reason about |
| Greedy Bit Filtering + BFS | O(32*m*n) | O(m*n) | Optimal approach when minimizing OR value bit by bit |
Frequently asked questions
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.