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

Master LeetCode problem 1981 (Minimize the Difference Between Target and Chosen Elements), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1981. Minimize the Difference Between Target and Chosen Elements

Medium

Array Dynamic Programming Matrix

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming to keep track of all possible sums that can be obtained by choosing one element from each row in the matrix. We can start from the first row and update the possible sums for the next row by adding the current row's elements to the previous sums. By the end of the iteration, we will have all possible sums in the last row.

Then, we can iterate through the last row to find the sum closest to the target. This closest sum will give us the minimum absolute difference between the target and the chosen elements.

The time complexity of this approach is O(m * n * 70) where m is the number of rows, n is the number of columns, and 70 is the maximum value in the matrix. The space complexity is O(70) for storing the possible sums.

Solution Code

class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        int m = mat.length, n = mat[0].length;
        boolean[] dp = new boolean[800 * m + 1];
        dp[0] = true;
        
        for (int i = 0; i < m; i++) {
            boolean[] next = new boolean[800 * m + 1];
            for (int j = 0; j < 800 * m; j++) {
                if (!dp[j]) continue;
                for (int k = 0; k < n; k++) {
                    if (j + mat[i][k] <= 800 * m) {
                        next[j + mat[i][k]] = true;
                    }
                }
            }
            dp = next;
        }
        
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < 800 * m + 1; i++) {
            if (dp[i]) {
                ans = Math.min(ans, Math.abs(i - target));
            }
        }
        
        return ans;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1981 (Minimize the Difference Between Target and Chosen Elements)?

This page provides optimized solutions for LeetCode problem 1981 (Minimize the Difference Between Target and Chosen Elements) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1981 (Minimize the Difference Between Target and Chosen Elements)?

The time complexity for LeetCode 1981 (Minimize the Difference Between Target and Chosen Elements) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1981 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1981 in Java, C++, or Python.

Back to LeetCode Solutions