Minimize the Difference Between Target and Chosen Elements
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every possible combination of chosen elements, one from each row, to find the sum that is closest to the target. It uses a recursive backtracking method to generate all combinations.
Algorithm
- Initialize a global variable
minDifferenceto a very large value. - Define a recursive function
backtrack(row, currentSum). - The base case for the recursion is when
rowequals the total number of rowsm. At this point, a full combination has been chosen. Calculate the absolute differenceabs(currentSum - target)and updateminDifferenceif this new difference is smaller. - In the recursive step, for the current
row, iterate through each elementmat[row][j]fromj = 0ton-1. - For each element, make a recursive call
backtrack(row + 1, currentSum + mat[row][j])to explore the next level of choices. - The initial call to start the process is
backtrack(0, 0). - After the initial call returns,
minDifferencewill hold the minimum possible absolute difference.
Walkthrough
We define a recursive function, say backtrack(row, currentSum), where row is the current row index we are considering and currentSum is the sum of elements chosen from previous rows. The function works as follows:
When we are at a certain row, we iterate through all its elements. For each element, we add it to the currentSum and recursively call the function for the next row (row + 1).
The recursion stops when we have processed all the rows (i.e., row == m). At this base case, we have a complete sum from one element per row. We then compute the absolute difference between this sum and the target and update our global minimum difference if the current one is smaller.
This method exhaustively checks every single one of the n^m possible combinations.
Complexity
Time
O(n^m) For each of the `m` rows, we have `n` choices. This leads to a total of `n * n * ... * n` (`m` times) or `n^m` possible combinations to check. Given the constraints (`m, n <= 70`), this is computationally infeasible.
Space
O(m) The space complexity is determined by the maximum depth of the recursion stack, which is equal to the number of rows, `m`.
Trade-offs
Pros
Simple to understand and implement.
Conceptually straightforward.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
Solutions
Solution
class Solution {public int minimizeTheDifference(int[][] mat, int target) { Set<Integer> f = new HashSet<>(); f.add(0); for (var row : mat) { Set<Integer> g = new HashSet<>(); for (int a : f) { for (int b : row) { g.add(a + b); } } f = g; } int ans = 1 << 30; for (int v : f) { ans = Math.min(ans, Math.abs(v - target)); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.