One per Row, Close to the Goal

Medium

You are given an m × n matrix grid and an integer goal. Pick exactly one number from every row of the matrix and add the picked numbers together. Return the smallest possible value of |sum − goal|.

Example 1

grid=[[2, 9], [4, 1], [6, 3]], goal=12 → 0

Take 2, 4 and 6: the sum is 12, exactly the goal, so the gap is 0.

Example 2

grid=[[5, 6], [7, 8]], goal=30 → 16

The largest sum is 6 + 8 = 14, which falls short of 30 by 16.

Example 3

grid=[[10, 20, 30]], goal=24 → 4

Constraints

1 ≤ m, n ≤ 70
1 ≤ grid[i][j] ≤ 70
1 ≤ goal ≤ 800

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Matrix

Similar problems

Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium Largest Solid Square Medium Best Spot for the Turret Medium Steps to the Nearest Zero Medium

Input

grid=[[2, 9], [4, 1], [6, 3]], goal=12

Expected

Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.