Minimize the difference between target and chosen elements

Array Dynamic Programming Matrix

36.7% acceptance

Feb 25, 2026

1060

145

You are given an m x n integer matrix mat and an integer target. Choose one integer from each row in the matrix such that the absolute difference between target and the sum of the chosen elements is minimized. Return the minimum absolute difference. The absolute difference between two numbers a and b is the absolute value of a - b.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimize_the_difference(mat: Vec<Vec<i32>>, target: i32) -> i32 {
    // Use bitset DP: track all possible sums
    // Max possible sum = 70 * 70 = 4900
    let max_sum = 4900;
    let mut possible = vec![false; max_sum + 1];
    possible[0] = true;
    
    for row in &mat {
      let mut next = vec![false; max_sum + 1];
      for &val in row {
        let v = val as usize;
        for s in 0..=max_sum - v {
          if possible[s] {
            next[s + v] = true;
          }
        }
      }
      possible = next;
    }
    
    let mut ans = i32::MAX;
    for s in 0..=max_sum {
      if possible[s] {
        ans = ans.min((s as i32 - target).abs());
      }
    }
    ans
  }
}