Minimize the Difference Between Target and Chosen Elements LeetCode solution in Python

1
class Solution:
2
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
3

4
        # store the mxn size of the matrix
5
        m = len(mat)
6
        n = len(mat[0])
7

8
        dp = defaultdict(defaultdict)
9

10
        # Sorting each row of the array for more efficient pruning
11
        # Note:this purely based on the observation on problem constraints (although interesting :))
12
        for i in range(m):
13
            mat[i] = sorted(mat[i])
14

15
        # returns minimum absolute starting from from row i to n-1 for the target
16
        globalMin = float("inf")
17

18
        def findMinAbsDiff(i, prevSum):
19
            nonlocal globalMin
20
            if i == m:
21
                globalMin = min(globalMin, abs(prevSum - target))
22
                return abs(prevSum - target)
23

24
            # pruning step 1
25
            # because the array is increasing & prevSum & target will always be positive
26
            if prevSum - target > globalMin:
27
                return float("inf")
28

29
            if (i in dp) and (prevSum in dp[i]):
30
                return dp[i][prevSum]
31

32
            minDiff = float("inf")
33
            # for each candidate select that and backtrack
34
            for j in range(n):
35
                diff = findMinAbsDiff(i + 1, prevSum + mat[i][j])
36
                # pruning step 2 - break if we found minDiff 0 --> VERY CRTICIAL
37
                if diff == 0:
38
                    minDiff = 0
39
                    break
40
                minDiff = min(minDiff, diff)
41

42
            dp[i][prevSum] = minDiff
43
            return minDiff
44

45
        return findMinAbsDiff(0, 0)