Skip to content

1981. Minimize the Difference Between Target and Chosen Elements 👍

  • Time: $O(m \cdot 70^2)$
  • Space: $O(m \cdot 70^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int minimizeTheDifference(vector<vector<int>>& mat, int target) {
    const int minSum = getMinSum(mat);
    if (minSum >= target)  // No need to consider any larger combination.
      return minSum - target;

    const int maxSum = getMaxSum(mat);
    vector<vector<int>> mem(mat.size(), vector<int>(maxSum + 1, -1));
    return minimizeTheDifference(mat, 0, 0, target, mem);
  }

 private:
  int minimizeTheDifference(const vector<vector<int>>& mat, int i, int sum,
                            int target, vector<vector<int>>& mem) {
    if (i == mat.size())
      return abs(sum - target);
    if (mem[i][sum] != -1)
      return mem[i][sum];
    int res = INT_MAX;
    for (const int num : mat[i])
      res = min(res, minimizeTheDifference(mat, i + 1, sum + num, target, mem));
    return mem[i][sum] = res;
  }

  int getMinSum(const vector<vector<int>>& mat) {
    return accumulate(mat.begin(), mat.end(), 0,
                      [](int subtotal, const vector<int>& row) {
      return subtotal + ranges::min(row);
    });
  }

  int getMaxSum(const vector<vector<int>>& mat) {
    return accumulate(mat.begin(), mat.end(), 0,
                      [](int subtotal, const vector<int>& row) {
      return subtotal + ranges::max(row);
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int minimizeTheDifference(int[][] mat, int target) {
    final int minSum = Arrays.stream(mat).mapToInt(A -> Arrays.stream(A).min().getAsInt()).sum();
    if (minSum >= target) // No need to consider any larger combination.
      return minSum - target;

    final int maxSum = Arrays.stream(mat).mapToInt(A -> Arrays.stream(A).max().getAsInt()).sum();
    Integer[][] mem = new Integer[mat.length][maxSum + 1];
    return minimizeTheDifference(mat, 0, 0, target, mem);
  }

  private int minimizeTheDifference(int[][] mat, int i, int sum, int target, Integer[][] mem) {
    if (i == mat.length)
      return Math.abs(sum - target);
    if (mem[i][sum] != null)
      return mem[i][sum];
    int res = Integer.MAX_VALUE;
    for (final int num : mat[i])
      res = Math.min(res, minimizeTheDifference(mat, i + 1, sum + num, target, mem));
    return mem[i][sum] = res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def minimizeTheDifference(self, mat: list[list[int]], target: int) -> int:
    minSum = sum(min(row) for row in mat)
    if minSum >= target:  # No need to consider any larger combination.
      return minSum - target

    @functools.lru_cache(None)
    def dp(i: int, summ: int) -> int:
      if i == len(mat):
        return abs(summ - target)
      return min(dp(i + 1, summ + num) for num in mat[i])

    return dp(0, 0)