Minimize the Difference Between Target and Chosen Elements solution and explanation
Google
7 more videos on this problem
LeetCode 1981. Minimize the Difference Between Target and Chosen ElementsHappy Coding · 9:52 · 2K views
Minimize the Difference Between Target and Chosen Elements | Leetcode 1981 | DP | DSATejpratap Pandey · 6:12 · 1K views
1981. Minimize the Difference Between Target and Chosen Elements (Leetcode Medium)Programming Live with Larry · 19:17 · 1K views
Minimize the Difference Between Target and Chosen Elements | Bitset C++Hitesh Tripathi · 17:36 · 1K views
Minimize the Difference Between Target and Chosen Elements (Leetcode 1981)Algorithms Casts · 27:38 · 1K views
【每日一题】LeetCode 1981. Minimize the Difference Between Target and Chosen Elements, 9/2/2021Huifeng Guan · 20:37 · 951 views
Leetcode 1981. Minimize the Difference Between Target and Chosen Elements (group knapsack)LetsCode · 10:45 · 53 views
LeetCode 1981: Minimize the Difference Between Target and Chosen ElementsAlitaCode · 27:11 · 9 views
The problem
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.
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.lengthn == mat[i].length1 <= m, n <= 701 <= mat[i][j] <= 701 <= target <= 800
Approach overview
Problem Overview: You are given an m x n matrix and a target value. You must choose exactly one element from each row. The goal is to minimize |sum - target|, where sum is the total of the chosen elements.
Approach 1: Backtracking with Pruning (Exponential, worst-case O(n^m) time, O(m) space)
This approach tries every possible combination by selecting one element from each row using recursion. At each step, you add the chosen value to the current sum and move to the next row. A pruning rule cuts off branches when the current sum already exceeds a threshold where improvement is impossible. Sorting row values and stopping early once sums grow too large significantly reduces the search space in practice. The method is straightforward and works well for smaller matrices but can still degrade toward exponential complexity in the worst case.
Approach 2: Dynamic Programming with Closure Check (O(m * n * S) time, O(S) space)
The optimal solution uses dynamic programming to track reachable sums after processing each row. Start with a set containing 0. For every row, iterate through the current sums and add each element in that row, generating the next set of possible sums. To prevent the state space from exploding, apply a closure check: cap the sums at a reasonable bound around the target (for example target + 70, since matrix values are small). This pruning keeps the DP state compact while still preserving all sums that could produce the optimal difference.
The key insight: the exact sum doesn't matter once it grows far beyond the target. Only sums within a limited range can produce the minimum absolute difference. Using a boolean array or hash set to represent reachable sums keeps transitions fast. Each row performs a simple nested iteration over current sums and row elements, making the implementation clean and predictable.
This technique is a classic pattern for subset-style problems where the number of combinations is large but the sum range is bounded. It appears frequently in array and matrix problems that involve selecting elements under constraints.
Recommended for interviews: Dynamic programming with closure checking. Interviewers expect you to recognize that brute-force combinations are too large and convert the problem into a bounded sum DP. Showing the backtracking approach first demonstrates problem understanding, but the DP optimization shows stronger algorithmic thinking.
Approach 1: Dynamic Programming with Closure Check
This approach uses a dynamic programming table to keep track of all possible sums we can achieve with the elements from the first i rows up to a certain maximum value. At each row, we add each number in that row to all possible sums from the previous row, ensuring to keep the solutions optimized by only storing possible sums that bring us closer to the target.
def minimizeTheDifference(mat, target):
m, n = len(mat), len(mat[0])
possible_sums = {0}
for i in range(m):
possible_sums = {a + b for a in possible_sums for b in mat[i]}
return min(abs(target - s) for s in possible_sums)#include <vector>
#include <set>
#include <cmath>
using namespace std;
class Solution {
public:
int minimizeTheDifference(vector<vector<int>>& mat, int target) {
set<int> possibleSums = {0};
for (const auto& row : mat) {
set<int> newSums;
for (const int& num : row) {
for (const int& s : possibleSums) {
newSums.insert(s + num);
}
}
possibleSums = move(newSums);
}
int minDiff = INT_MAX;
for (const int& s : possibleSums) {
minDiff = min(minDiff, abs(target - s));
}
return minDiff;
}
};This Python function iterates through each row of the matrix, calculating all the possible sums one can generate using numbers up to the current row. The goal is to find the sum that leads to the smallest absolute difference from the target. By working through each row, we use a set to ensure unique and possible sums, thereby optimizing our calculations.
Time Complexity: O(m * n * n) because for each of the m rows, we're recalculating across n elements with the running sum set of at most n growth in complexity terms. Space Complexity: O(kn) where k is the maximum possible sum trackable at each step, kept within practical limits by problem constraints.
Approach 2: Backtracking with Pruning
This approach utilizes backtracking to explore each possible selection choice exhaustively and prune unneeded branches. It builds sums row by row and branches only when potential can minimize the absolute target difference calculated dynamically.
class Solution {
public int minimizeTheDifference(int[][] mat, int target) {
return backtrack(mat, target, 0, 0, new Integer[mat.length][target + 1]);
}
private int backtrack(int[][] mat, int target, int row, int currSum, Integer[][] memo) {
if (row == mat.length) {
return Math.abs(currSum - target);
}
if (memo[row][currSum % (target + 1)] != null) {
return memo[row][currSum % (target + 1)];
}
int minDiff = Integer.MAX_VALUE;
for (int num : mat[row]) {
minDiff = Math.min(minDiff, backtrack(mat, target, row + 1, currSum + num, memo));
if (minDiff == 0) break; // Perfect match found
}
return memo[row][currSum % (target + 1)] = minDiff;
}
}var minimizeTheDifference = function(mat, target) {
let memo = {};
const dfs = (row, currSum) => {
if (row === mat.length) return Math.abs(currSum - target);
const key = `${row},${currSum}`;
if (key in memo) return memo[key];
let minDiff = Infinity;
for (let num of mat[row]) {
minDiff = Math.min(minDiff, dfs(row + 1, currSum + num));
if (minDiff === 0) break;
}
return memo[key] = minDiff;
}
return dfs(0, 0);
};This Java solution implements backtracking by recursively choosing each row's elements to form a sum. It uses memoization to avoid recalculating previously explored states, thus pruning unnecessary calculations and enhancing efficiency.
Time Complexity: O(n^m), because each choice might lead to all subsequent options. Space Complexity: O(m * t), employing a basic memoization table dependent on target constraint values for optimization.
Approach 3: Dynamic Programming (Grouped Knapsack)
Let f[i][j] represent whether it is possible to select elements from the first i rows with a sum of j. Then we have the state transition equation:
$
f[i][j] = \begin{cases} 1 & if there exists x \in row[i] such that f[i - 1][j - x] = 1 \ 0 & otherwise \end{cases}
where row[i] represents the set of elements in the i-th row.
Since f[i][j] is only related to f[i - 1][j], we can use a rolling array to optimize the space complexity.
Finally, we traverse the f array to find the smallest absolute difference.
The time complexity is O(m^2 times n times C) and the space complexity is O(m times C). Here, m and n are the number of rows and columns of the matrix, respectively, and C$ is the maximum value of the matrix elements.
func minimizeTheDifference(mat [][]int, target int) int {
f := []int{1}
for _, row := range mat {
mx := slices.Max(row)
g := make([]int, len(f)+mx)
for _, x := range row {
for j := x; j < len(f)+x; j++ {
g[j] |= f[j-x]
}
}
f = g
}
ans := 1 << 30
for j, v := range f {
if v == 1 {
ans = min(ans, abs(j-target))
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Closure Check | Time Complexity: O(m * n * n) because for each of the m rows, we're recalculating across n elements with the running sum set of at most n growth in complexity terms. Space Complexity: O(kn) where k is the maximum possible sum trackable at each step, kept within practical limits by problem constraints. |
| Backtracking with Pruning | Time Complexity: O(n^m), because each choice might lead to all subsequent options. Space Complexity: O(m * t), employing a basic memoization table dependent on target constraint values for optimization. |
| Dynamic Programming (Grouped Knapsack) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Pruning | O(n^m) worst case | O(m) | Useful for understanding the brute-force search and when matrix size is small |
| Dynamic Programming with Closure Check | O(m * n * S) | O(S) | Best general solution when sum range is bounded around the target |
Frequently asked questions
Is Minimize the Difference Between Target and Chosen Elements easy or hard?
The problem is rated Medium on LeetCode. The challenge lies in recognizing that brute-force combinations are exponential and converting the problem into a bounded dynamic programming formulation.
Minimize the Difference Between Target and Chosen Elements Python/Java solution
Python and C++ implementations typically use a set or boolean DP array to store reachable sums and prune values above a threshold. Java or JavaScript solutions often implement the same idea with sets or backtracking with pruning depending on constraints.
How to solve Minimize the Difference Between Target and Chosen Elements in O(n)?
A strict O(n) solution is not possible because you must consider combinations across rows. The closest efficient method is dynamic programming over possible sums, which runs in O(m * n * S) time where S is the limited sum range near the target.
What is the best approach for Minimize the Difference Between Target and Chosen Elements?
Dynamic programming with a bounded sum set is the most effective approach. Track all reachable sums after each matrix row and prune sums that grow far beyond the target. This keeps the state space small while guaranteeing the optimal absolute difference.
Is Minimize the Difference Between Target and Chosen Elements asked at Google/Amazon/Meta?
Matrix and dynamic programming problems similar to this frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of subset-sum style DP with pruning are common evaluation topics in algorithm rounds.
What data structure is used in Minimize the Difference Between Target and Chosen Elements?
The core data structure is a boolean array or hash set that tracks reachable sums after processing each row. This structure allows constant-time membership checks and efficient iteration while building the next state.
What is the time complexity of Minimize the Difference Between Target and Chosen Elements?
The optimized dynamic programming solution runs in O(m * n * S) time, where m is the number of rows, n is the number of columns, and S is the bounded sum range near the target. Space complexity is O(S) because only the reachable sums for the current step are stored.