#1981 - Minimize the Difference Between Target and Chosen Elements

Medium • View on LeetCode • View on GitHub

Problem Description

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

/**
 * @param {number[][]} mat
 * @param {number} target
 * @return {number}
 */
var minimizeTheDifference = function(mat, target) {
  const m = mat.length;
  const maxSum = 70 * m;
  let possibleSums = new Set([0]);

  for (const row of mat) {
    const nextSums = new Set();
    for (const num of row) {
      for (const sum of possibleSums) {
        const newSum = sum + num;
        if (newSum <= target + maxSum) {
          nextSums.add(newSum);
        }
      }
    }
    possibleSums = nextSums;
  }

  let result = Infinity;
  for (const sum of possibleSums) {
    result = Math.min(result, Math.abs(sum - target));
  }

  return result;
};