Skip to content

Practice Minimize the Difference Between Target and Chosen Elements

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#1981
LeetCode Problem

Minimize the Difference Between Target and Chosen Elements

Problem Statement

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.

Source: Minimize the Difference Between Target and Chosen Elements on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
Output
0
Explanation

Choose 1 from the first row, 4 from the second and 8 from the third. Their sum is 13, exactly the target, so the absolute difference is zero and cannot be improved. Each row must contribute exactly one value. A dynamic program can retain all reachable sums after each row; selecting the locally closest value from each row independently would ignore how later choices combine.

# Example 2

Input
mat = [[1],[2],[3]], target = 100
Output
94
Explanation

Every row contains only one value, so the sole allowed selection is 1, 2 and 3. Its sum is 6 and the difference from the target is |100 - 6| = 94. Each row contributes its single entry; no row can be selected twice or skipped. This example also shows why a reachable sum far below the target must remain a valid answer when no closer selection exists.

# Example 3

Input
mat = [[1,2,9,8,7]], target = 6
Output
1
Explanation

With only one row, exactly one value may be selected. The differences from 6 for [1, 2, 9, 8, 7] are [5, 4, 3, 2, 1]. Choosing 7 gives the minimum difference of 1. A sum above the target is allowed; restricting the search to sums at most the target would incorrectly choose 2 and return 4.

Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 70
1 <= mat[i][j] <= 70
1 <= target <= 800

How to solve Minimize the Difference Between Target and Chosen Elements

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

The set of sums reachable after each row is small and bounded (at most 70 times 70 = 4900), so tracking reachable sums as a bitset row by row explores every combination implicitly, and among sums already at or above target only the smallest needs to be kept.

Why brute force is not enough

Enumerating one element per row is n^m choices, up to 70^70, and even memoizing on (row, sum) without pruning is wasteful once you see that sums, not choices, are the real state.

Approach

  1. Start with the reachable set containing only 0 before any row is processed.
  2. For each row, build the next reachable set by adding every distinct value in the row to every sum in the current set; deduplicate the row's values first because repeats add nothing.
  3. Prune: among new sums that are at or above target, keep only the smallest, because all later additions are positive and can only push larger sums further from target.
  4. The invariant is that the set after row i contains every sum of one element from each of the first i rows that could still lead to an optimal answer.
  5. After the last row, scan the set and return the minimum absolute difference from target, exiting early if a difference of 0 appears.

Walkthrough of Example 1

mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13 → 0

  1. Row [1,2,3] turns {0} into {1, 2, 3}.
  2. Row [4,5,6] produces {5, 6, 7, 8, 9}; all are below 13, so nothing is pruned.
  3. Row [7,8,9] produces 12 through 18; 13 is reachable, for example 2 + 4 + 7 or 1 + 4 + 8, and the sums 14 through 18 would be pruned in favor of 13.
  4. The closest sum to 13 is 13 itself, so the answer is 0.

Time and space

Time O(m * n * S) · Space O(S). m is the number of rows, n the number of columns, and S the bound on tracked sums, about target plus the largest element after pruning (at most 870) or 4900 without; each row combines each distinct value with each tracked sum.

Interview pitfalls

  • Pruning every sum above target, which breaks example 3 where 7 is closer to 6 than 2 is; keep the smallest over-target sum.
  • Sizing the bitset by target rather than by the maximum possible sum of 4900 when not pruning.
  • Greedily taking the value closest to the remaining target in each row instead of tracking all sums.
  • Not deduplicating row values, which multiplies work on rows full of repeats.
  • Forgetting that the single kept over-target sum still competes for the final answer.

Follow-up questions interviewers ask

  • What if matrix values could be negative or zero, invalidating the pruning argument?
  • How would you return the chosen elements, not just the difference?
  • If target were far larger than the maximum possible sum, how would you short-circuit?

Further reading on the technique: Dynamic programming

Related LeetCode Problems

Practice more problems similar to Minimize the Difference Between Target and Chosen Elements.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.