Minimize the Difference Between Target and Chosen Elements Solution
Minimize the Difference Between Target and Chosen Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimize the Difference Between Target and Chosen Elements is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n integer matrix mat and an integer target. Pick exactly one element from every row and add the picked elements up.
Return the smallest possible value of |sum - target|.
Example 1
Input: mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
Output: 0
Explanation: 1 + 5 + 7 = 13.
Example 2
Input: mat = [[2,5],[3,7]], target = 11
Output: 1
Explanation: Reachable sums are 5, 8, 9 and 12; 12 is closest.
Example 3
Input: mat = [[1],[2],[3]], target = 100
Output: 94
Constraints
m == mat.lengthn == mat[i].length1 <= m, n <= 701 <= mat[i][j] <= 701 <= target <= 800
Hints for Minimize the Difference Between Target and Chosen Elements
Hint 1
Values and row counts are small, so the set of reachable sums is small too (at most 70 · 70).
Hint 2
Process row by row, turning the set of sums reachable so far into the set after picking one value from the next row.
Hint 3
Sums above
targetonly get worse as more rows are added — of those, keep only the smallest one.
How to solve Minimize the Difference Between Target and Chosen Elements
A subset-sum style DP over rows. Track which partial sums are reachable; because every element is positive, a partial sum that already exceeds target can only drift further away, so among those it suffices to remember the minimum.
Approach
- Keep a boolean array
reach[0..target](start withreach[0] = true) andover= the smallest reachable partial sum abovetarget(start: none). - For each row: new
over= oldover+ the row's minimum (if oldoverexists). For each reachablesand each valuevin the row: ifs + v <= targetmark it in the new array, otherwise update the newoverwiths + v. - After the last row the answer is the smaller of
target - (largest reachable s)andover - target.
Why it works
All partial sums up to target are tracked exactly. Any final sum built from a partial sum p > target is at least p plus the remaining rows' minima, which is minimised by the smallest such p — so dropping the other over-target sums never loses the optimum.
Complexity
- Time —
O(m · n · target) - Space —
O(target)
Pitfalls
- Every row must contribute exactly one element — skipping a row is not allowed.
- Without the cap, the set of sums can reach 4,900 values per row; it is still fine, but the cap makes it tighter.
- Do not prune sums below
targetgreedily — a smaller partial sum can still end closer.
Reference solution
Python
from typing import List
def minimizeTheDifference(mat: List[List[int]], target: int) -> int:
reach = {0}
for row in mat:
vals = set(row)
nxt = set()
over = None
for s in reach:
for v in vals:
t = s + v
if t <= target:
nxt.add(t)
elif over is None or t < over:
over = t
if over is not None:
nxt.add(over)
reach = nxt
return min(abs(s - target) for s in reach)Java
public static int minimizeTheDifference(int[][] mat, int target) {
final int INF = 1000000000;
boolean[] reach = new boolean[target + 1];
reach[0] = true;
int over = INF;
for (int[] row : mat) {
int rowMin = INF;
for (int v : row) rowMin = Math.min(rowMin, v);
boolean[] nxt = new boolean[target + 1];
int nOver = over == INF ? INF : over + rowMin;
for (int s = 0; s <= target; s++) {
if (!reach[s]) continue;
for (int v : row) {
int t = s + v;
if (t <= target) nxt[t] = true;
else if (t < nOver) nOver = t;
}
}
reach = nxt;
over = nOver;
}
int best = over == INF ? INF : over - target;
for (int s = 0; s <= target; s++) if (reach[s] && target - s < best) best = target - s;
return best;
}C++
int minimizeTheDifference(vector<vector<int>>& mat, int target) {
const int INF = 1000000000;
vector<char> reach(target + 1, 0);
reach[0] = 1;
int over = INF;
for (auto& row : mat) {
int rowMin = *min_element(row.begin(), row.end());
vector<char> nxt(target + 1, 0);
int nOver = over == INF ? INF : over + rowMin;
for (int s = 0; s <= target; s++) {
if (!reach[s]) continue;
for (int v : row) {
int t = s + v;
if (t <= target) nxt[t] = 1;
else if (t < nOver) nOver = t;
}
}
reach = nxt;
over = nOver;
}
int best = over == INF ? INF : over - target;
for (int s = 0; s <= target; s++) if (reach[s] && target - s < best) best = target - s;
return best;
}JavaScript
var minimizeTheDifference = function(mat, target) {
var INF = 1000000000;
var reach = new Array(target + 1).fill(false);
reach[0] = true;
var over = INF;
for (var r = 0; r < mat.length; r++) {
var row = mat[r];
var rowMin = INF;
for (var c = 0; c < row.length; c++) if (row[c] < rowMin) rowMin = row[c];
var nxt = new Array(target + 1).fill(false);
var nOver = over === INF ? INF : over + rowMin;
for (var s = 0; s <= target; s++) {
if (!reach[s]) continue;
for (c = 0; c < row.length; c++) {
var t = s + row[c];
if (t <= target) nxt[t] = true;
else if (t < nOver) nOver = t;
}
}
reach = nxt;
over = nOver;
}
var best = over === INF ? INF : over - target;
for (s = 0; s <= target; s++) if (reach[s] && target - s < best) best = target - s;
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming