Problem statement

https://leetcode.com/problems/minimize-the-difference-between-target-and-chosen-elements/

Solution

The idea is that our numbers are very small: mat[i][j] <= 70, and also m, n <= 70. It means, tha final sum of all numbers can be no more than 70**2.

So, we can do almost bruteforce solution: iterate over rows and keep in nums all possible sums we get so far.

Complexity

Each time we have in nums no more than 70**2 elements and we travere it not more than 70 rows, each of which have no more than 70 elements so final complexity is O(n^4), where n = 70. Then we need to find closes element to target which is just O(n^3). Space complexity is O(n^3). It was AC during contest for me, however now it gives TLE.

class Solution:
    def minimizeTheDifference(self, mat, target):
        nums = {0}
        for row in mat:
            nums = {x + i for x in row for i in nums}
        
        return min(abs(target - x) for x in nums)

Solution 2

We can optimize solutoin, taking into account that we need to look around target. That is if minimal sum of all numbers is more than target, we do no have choice: we need to take it. In the opposite case no need to go higher than 2*target - possible_min

Complexity

Time complexity is O(target * n^2) now, space is O(target).

Code

class Solution:
    def minimizeTheDifference(self, mat, target):
        possible_min = sum(min(row) for row in mat)
        if possible_min > target: return possible_min - target
        
        nums = {0}
        for row in mat:
            nums = {x + i for x in row for i in nums if x + i <= 2*target - possible_min}
        
        return min(abs(target - x) for x in nums)