Minimize the Difference Between Target and Chosen Elements

Medium
1486.

Minimize the Difference Between Target and Chosen Elements

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.

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.length
  • n == mat[i].length
  • 1 <= m, n <= 70
  • 1 <= mat[i][j] <= 70
  • 1 <= target <= 800
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @param {number} target
 * @return {number}
 */
var minimizeTheDifference = function(mat, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • n == mat[i].length
  • 1 <= m, n <= 70
  • 1 <= mat[i][j] <= 70
  • 1 <= target <= 800

Hints for Minimize the Difference Between Target and Chosen Elements

  1. Hint 1

    Values and row counts are small, so the set of reachable sums is small too (at most 70 · 70).

  2. 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.

  3. Hint 3

    Sums above target only 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

  1. Keep a boolean array reach[0..target] (start with reach[0] = true) and over = the smallest reachable partial sum above target (start: none).
  2. For each row: new over = old over + the row's minimum (if old over exists). For each reachable s and each value v in the row: if s + v <= target mark it in the new array, otherwise update the new over with s + v.
  3. After the last row the answer is the smaller of target - (largest reachable s) and over - 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 target greedily — 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