LeetCode 1981 - Minimize the Difference Between Target and Chosen Elements

LeetCode Problem 1981

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem asks us to select exactly one element from each row of a given m x n integer matrix mat such that the sum of the selected elements is as close as possible to a given integer target. The goal is to minimize the absolute difference between the sum of chosen elements and the target.

In simpler terms, we are trying to form a sum from the matrix, picking one number per row, so that this sum is near the target. The input guarantees that the matrix dimensions m and n are both between 1 and 70, and each element of the matrix and the target value are all positive integers. This tells us that a brute-force solution that tries all combinations (which could be up to 70^70 possibilities in the worst case) is infeasible.

Key points to note include edge cases where the target is much smaller than the minimum possible sum or much larger than the maximum possible sum, or where the matrix has only one row or one column. These cases could potentially trip up naive implementations if they assume more rows or uniform distribution of numbers.

Approaches

Brute Force

A brute-force approach would enumerate all possible combinations of choosing one element from each row, calculate their sums, and keep track of the sum that has the smallest absolute difference to target. While this approach is correct, it is computationally infeasible for the given constraints because the number of combinations grows exponentially with the number of rows, O(n^m).

Optimal Approach

The key insight for an optimal solution is to use dynamic programming. Instead of keeping track of all combinations explicitly, we maintain a set of all possible sums after processing each row. For each row, we update the set of sums by adding each element in the row to each sum from the previous row. After processing all rows, we scan all sums to find the one closest to the target.

To keep the state manageable, we can use a set to automatically handle duplicates, since multiple paths can lead to the same sum. Python's set or Go's map[int]struct{} works well here. This approach is efficient because the maximum possible sum is bounded (m * max(mat[i][j]) ≤ 4900), which is small enough to handle with sets.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^m)	O(1)	Enumerates all possible combinations; exponential and infeasible
Dynamic Programming	O(m * n * S)	O(S)	Maintains reachable sums iteratively; S is sum range capped by m*70

Algorithm Walkthrough

1. Initialize a set possible_sums containing just 0, representing the sum before processing any row.
2. Iterate through each row in the matrix.
3. For the current row, create a new set next_sums to store all sums possible after including one element from this row.
4. For each sum s in possible_sums, add each element num from the current row to s, and add the result to next_sums.
5. After processing the row, update possible_sums to next_sums.
6. After processing all rows, find the sum in possible_sums that has the smallest absolute difference to target.
7. Return this minimum absolute difference.

Why it works: The algorithm keeps track of all reachable sums row by row. By using a set, duplicates are removed, preventing unnecessary computations. After processing all rows, the set contains all possible sums achievable by picking one element per row, guaranteeing that the minimum absolute difference is found.

Python Solution

from typing import List

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        possible_sums = {0}
        for row in mat:
            next_sums = set()
            for s in possible_sums:
                for num in row:
                    next_sums.add(s + num)
            possible_sums = next_sums
        return min(abs(s - target) for s in possible_sums)

The Python implementation uses a set to efficiently store reachable sums. For each row, we compute new sums by adding each row element to each sum already in the set. Finally, we compute the minimum absolute difference by iterating over the final set.

Go Solution

func minimizeTheDifference(mat [][]int, target int) int {
    possibleSums := map[int]struct{}{0: {}}
    
    for _, row := range mat {
        nextSums := make(map[int]struct{})
        for s := range possibleSums {
            for _, num := range row {
                nextSums[s+num] = struct{}{}
            }
        }
        possibleSums = nextSums
    }
    
    minDiff := 1 << 30 // large initial value
    for s := range possibleSums {
        diff := s - target
        if diff < 0 {
            diff = -diff
        }
        if diff < minDiff {
            minDiff = diff
        }
    }
    
    return minDiff
}

In Go, a map is used to simulate a set. The algorithm is identical to Python but explicitly handles absolute differences using standard integer arithmetic.

Worked Examples

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

• Initial possible_sums = {0}
• After first row: {1, 2, 3}
• After second row: {5,6,7,8,9}
• After third row: {12,13,14,15,16,17,18}
• Minimum absolute difference to 13: 0 (sum = 13)

Example 2: mat = [[1],[2],[3]], target = 100

• Initial possible_sums = {0}
• After each row: {1}, {3}, {6}
• Minimum absolute difference to 100: 94 (sum = 6)

Example 3: mat = [[1,2,9,8,7]], target = 6

• Only one row, possible sums: {1,2,7,8,9}
• Minimum absolute difference to 6: 1 (sum = 7)

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n * S)	For each row (m) and each element (n), we update a set of sums, where S is bounded by m*70
Space	O(S)	We store all reachable sums, which is at most m * max(mat[i][j])

The complexity is manageable because S (maximum possible sum) is limited to 70 * 70 = 4900, and sets avoid redundant computations.

Test Cases

# Provided examples
assert Solution().minimizeTheDifference([[1,2,3],[4,5,6],[7,8,9]], 13) == 0  # exact match
assert Solution().minimizeTheDifference([[1],[2],[3]], 100) == 94           # large target
assert Solution().minimizeTheDifference([[1,2,9,8,7]], 6) == 1              # single row

# Edge cases
assert Solution().minimizeTheDifference([[1]], 1) == 0                        # single element, matches target
assert Solution().minimizeTheDifference([[70]*70]*70, 800) == 10             # large uniform matrix
assert Solution().minimizeTheDifference([[1,2],[3,4]], 0) == 4               # target smaller than any sum
assert Solution().minimizeTheDifference([[1,2],[3,4]], 100) == 94            # target larger than any sum

Test	Why
Exact match	Validates finding sum equal to target
Large target	Validates difference computation when target is much larger than sum
Single row	Tests edge case of only one row
Single element	Minimal input size
Large uniform matrix	Tests performance on upper bound
Target smaller than min sum	Ensures algorithm handles sums always above target
Target larger than max sum	Ensures algorithm handles sums always below target

Edge Cases

1. Single Row Matrix: If the matrix has only one row, the result is simply the element closest to the target. The algorithm handles this by processing one row and computing the minimum absolute difference.
2. Target Smaller than Minimum Sum: If the target is smaller than the sum of the minimum elements of each row, the algorithm still works because the set of possible sums captures all achievable sums, and the minimum absolute difference is computed correctly.
3. Target Larger than Maximum Sum: Similarly, if the target exceeds the maximum possible sum, the final set will contain the largest achievable sum, and the minimum absolute difference is correctly calculated as target - max_sum. The algorithm inherently accounts for this scenario without additional checks.