#1981

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimize the Difference Between Target and Chosen Elements

This problem asks to select one element per row to minimize the absolute difference from a target sum using dynamic programming.

array dynamic programming matrix

Problem Statement

You are given an m x n integer matrix mat and a target integer. Select exactly one element from each row so that the absolute difference between the sum of selected elements and the target is minimized.

Return the minimum absolute difference possible. Each row must contribute exactly one number, and your solution should efficiently explore all feasible sums using dynamic programming techniques.

Examples

Example 1

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

Output: 0

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

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

The best choice is to choose 7 from the first row. The absolute difference is 1.

Constraints

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

Solution Approach

Use a set for state tracking

Initialize a set with 0 to represent the sum of no elements. For each row, iterate over its elements and add them to all sums from the previous row, storing results in a new set. This tracks all reachable sums without duplicates, aligning with the state transition DP pattern.

Update sums row by row

For every element in the current row, combine it with each sum from the previous set. After processing the row, replace the previous set with the new set. This row-wise update ensures all possible sums are considered while keeping memory manageable.

Compute the minimum absolute difference

After all rows are processed, iterate over the final set of sums and calculate the absolute difference from the target. The smallest difference is the answer. This leverages the precomputed state transitions to efficiently find the optimal sum.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the range of sums tracked. Using a set to store reachable sums avoids redundant calculations. Worst-case complexity grows with m, n, and the possible sum range, but pruning with sets ensures feasible performance for the given constraints.

What Interviewers Usually Probe

They expect an understanding of state transition DP applied to multiple rows of a matrix.
They look for an efficient approach to track reachable sums without generating all combinations explicitly.
They may ask about trade-offs between time and space when storing intermediate sums in a set.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all possible combinations leads to exponential time and memory usage.
Failing to update the set properly row by row can miss valid sums.
Not considering the absolute difference correctly at the end may produce wrong results.

Follow-up variants

Maximize the sum not exceeding the target by adapting the DP update logic.
Handle negative numbers in the matrix by expanding the sum range tracked in the set.
Find the number of selections achieving the minimal difference instead of the difference itself.

FAQ

What is the main strategy for minimizing the difference to the target?

Use state transition dynamic programming with a set to track all possible sums row by row and select the sum closest to the target.

Can this problem be solved with simple recursion?

Recursion without memoization leads to exponential time; DP with sets efficiently prunes redundant sum combinations.

Why is a set used instead of a list for storing sums?

A set avoids duplicates, reducing memory usage and ensuring each reachable sum is considered only once in DP transitions.

How do constraints affect the DP approach?

Since m, n, and values are limited, the maximum sum is bounded, allowing the DP with sets to remain efficient without exploring all combinations.

Does this problem always require full matrix exploration?

No, using state transition DP with sum sets avoids exhaustive search while still capturing all reachable sums to minimize the absolute difference.

terminal

Solution

Solution 1: 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:

1

2

3

4

5

6

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        f = {0}
        for row in mat:
            f = set(a + b for a in f for b in row)
        return min(abs(v - target) for v in f)

Continue Practicing

#1937 maximum number of points with cost #2088 count fertile pyramids in a land #1728 cat and mouse ii