Problem Statement in English

You are given a matrix mat of size m x n and an integer target. The matrix contains integers, and you need to select one element from each row such that the absolute difference between the sum of the selected elements and the target is minimized.

You need to return the minimum absolute difference between the sum of the selected elements and the target.

Approach

The problem sounds and looks harder than it is. All you actually need to do is literally what the problem states.

Go row by row, and for each row, select one element. Keep track of the sum of the selected elements and compare it with the target to find the minimum absolute difference.

Apart from the set based optimisation to eliminate duplicates on the same row, there’s one other optimization we can make. If the path we’re taking is already worse than the best path we have found so far, we can stop exploring that path. This results in a 9000 ms improvement on LeetCode.

Solution in Python


class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        ROWS = len(mat)
        res = float("inf")

        @cache
        def dfs(row, s):
            nonlocal res

            if row >= ROWS:
                res = min(res, abs(target - s))
                return

            for col in mat[row]:
                newS = s + col
                if newS - target > res:
                    continue
                dfs(row + 1, newS)

        for i, row in enumerate(mat):
            mat[i] = set(row)

        dfs(0, 0)

        return res

Complexity

  • Time: $O(m * 2^n)$
    Where m is the number of rows and n is the maximum number of elements in any row. The time complexity arises from the recursive depth-first search (DFS) that explores all combinations of selecting one element from each row.

  • Space: $O(m * \text{sum(elements in the matrix)})$
    Since we are using memoization to store results for each row and sum combination, the space complexity is proportional to the number of rows and the possible sums.

Mistakes I Made

I had to look this one up :(

And we are done.