1981. Minimize the Difference Between Target and Chosen Elements LeetCode Solution

In this guide, you will get 1981. Minimize the Difference Between Target and Chosen Elements LeetCode Solution with the best time and space complexity. The solution to Minimize the Difference Between Target and Chosen Elements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimize the Difference Between Target and Chosen Elements solution in C++
  4. Minimize the Difference Between Target and Chosen Elements solution in Java
  5. Minimize the Difference Between Target and Chosen Elements solution in Python
  6. Additional Resources
1981. Minimize the Difference Between Target and Chosen Elements LeetCode Solution image

Problem Statement of Minimize the Difference Between Target and Chosen Elements

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.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
Output: 0
Explanation: One possible choice is to:
– Choose 1 from the first row.
– Choose 5 from the second row.
– Choose 7 from the third row.
The sum of the chosen elements is 13, which equals the target, so the absolute difference is 0.

Example 2:

Input: mat = [[1],[2],[3]], target = 100
Output: 94
Explanation: The best possible choice is to:
– Choose 1 from the first row.
– Choose 2 from the second row.
– Choose 3 from the third row.
The sum of the chosen elements is 6, and the absolute difference is 94.

See also  1559. Detect Cycles in 2D Grid LeetCode Solution

Example 3:

Input: mat = [[1,2,9,8,7]], target = 6
Output: 1
Explanation: The best choice is to choose 7 from the first row.
The absolute difference is 1.

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 70
1 <= mat[i][j] <= 70
1 <= target <= 800

Complexity Analysis

  • Time Complexity: O(m \cdot 70^2)
  • Space Complexity: O(m \cdot 70^2)

1981. Minimize the Difference Between Target and Chosen Elements LeetCode Solution in C++

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);
    });
  }
};
/* code provided by PROGIEZ */

1981. Minimize the Difference Between Target and Chosen Elements LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

1981. Minimize the Difference Between Target and Chosen Elements LeetCode Solution in Python

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)
# code by PROGIEZ

Additional Resources

See also  2003. Smallest Missing Genetic Value in Each Subtree LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.