Minimum bitwise or from grid

Array Greedy Bit Manipulation Matrix

26.0% acceptance

Mar 16, 2026

124

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_or(grid: Vec<Vec<i32>>) -> i32 {
    // Greedy bit-by-bit from high to low.
    // Try to unset each bit. If every row has an element fitting within the allowed mask, unset it.
    // O(17 * total_elements)
    let mut result = (1i32 << 17) - 1;
    for bit in (0..17).rev() {
      let candidate = result & !(1 << bit);
      let feasible = grid.iter().all(|row| {
        row.iter().any(|&v| v | candidate == candidate)
      });
      if feasible {
        result = candidate;
      }
    }
    result
  }
}