What is the time complexity of LeetCode 1981. Minimize the Difference Between Target and Chosen Elements?

The Python solution on this page runs in O(m^2 \times n \times C).

What is the space complexity of LeetCode 1981. Minimize the Difference Between Target and Chosen Elements?

The Python solution on this page uses O(m \times C) auxiliary space.

Minimize the Difference Between Target and Chosen Elements — LeetCode 1981 Python Solution

MediumArrayDynamic ProgrammingMatrix

Problem: #1981
Pattern: Matrix and Grid
Reading time: 2 min
Source: leetcode.com

The problem

You are given an m x n integer matrix mat and an integer target. Choose one integer from each row in the matrix such that the absolute difference between target and the sum of the chosen elements is minimized.

Example

Input: mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
Output: 0
Explanation: One possible choice is to:

Python solution

Python

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)

Complexity

Measure	Complexity
Time	O(m^2 \times n \times C)
Space	O(m \times C) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1981. Minimize the Difference Between Target and Chosen Elements is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1981. Minimize the Difference Between Target and Chosen Elements?: LeetCode 1981. Minimize the Difference Between Target and Chosen Elements is rated Medium on LeetCode.
What is the time complexity of LeetCode 1981. Minimize the Difference Between Target and Chosen Elements?: The Python solution on this page runs in O(m^2 \times n \times C).
What is the space complexity of LeetCode 1981. Minimize the Difference Between Target and Chosen Elements?: The Python solution on this page uses O(m \times C) auxiliary space.
What topics does LeetCode 1981. Minimize the Difference Between Target and Chosen Elements cover?: LeetCode 1981. Minimize the Difference Between Target and Chosen Elements is tagged Array, Dynamic Programming and Matrix on LeetCode.