Minimize the Difference Between Target and Chosen Elements

Minimize the Difference Between Target and Chosen Elements - 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.

Return the minimum absolute difference.

The absolute difference between two numbers a and b is |a - b|.

Input & Output

Example 1 — Perfect Match

$ Input: mat = [[1,2,3],[4,5,6]], target = 7

› Output: 1

💡 Note: Choose 1 from first row and 6 from second row: 1 + 6 = 7, but we can get closer with 2 + 5 = 7. Actually, the minimum difference is |7 - 6| = 1 when choosing 1 + 5 = 6.

Example 2 — Exact Target

$ Input: mat = [[1,2],[3,4]], target = 4

› Output: 0

💡 Note: Choose 1 from first row and 3 from second row: 1 + 3 = 4, which exactly equals target. Difference is |4 - 4| = 0.

Example 3 — Single Row

$ Input: mat = [[1,2,9,8,7]], target = 6

› Output: 1

💡 Note: With only one row, we must choose one element. The closest to 6 is 7, giving difference |6 - 7| = 1.

Constraints

m == mat.length
n == mat[i].length
1 ≤ m, n ≤ 70
1 ≤ mat[i][j] ≤ 70
1 ≤ target ≤ 800

Visualization

Tap to expand

Understanding the Visualization

Input

Matrix with rows and target value

Process

Select one element from each row

Output

Minimum absolute difference from target

Key Takeaway

🎯 Key Insight: Use dynamic programming to track all possible sums efficiently instead of trying every combination

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use dynamic programming to track all possible sums we can achieve by selecting one element from each row. The optimal approach uses a set to store possible sums and iteratively expands it for each row. Time: O(m × n × S), Space: O(S) where S is the number of unique sums.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Track Possible Sums	O(m × n × S)	O(S)	Use set-based DP to track all possible sums at each row and find the closest to target
Brute Force - Try All Combinations	O(n^m)	O(m)	Generate all possible combinations by choosing one element from each row
Memoization - Cache Intermediate Results	O(m × S)	O(m × S)	Use recursion with memoization to avoid recomputing the same subproblems

Dynamic Programming - Track Possible Sums — Algorithm Steps

Start with set containing only 0
For each row, generate new possible sums
Find sum in final set closest to target

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with sum = {0}

Expand

Add each row element to all current sums

Find

Find closest sum to target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_SUMS 100000

int possibleSums[MAX_SUMS];
int sumCount = 0;

void addSum(int sum) {
    for (int i = 0; i < sumCount; i++) {
        if (possibleSums[i] == sum) return;
    }
    if (sumCount < MAX_SUMS) {
        possibleSums[sumCount++] = sum;
    }
}

int solution(int** mat, int* colSizes, int rows, int target) {
    sumCount = 0;
    addSum(0);
    
    for (int r = 0; r < rows; r++) {
        int newSums[MAX_SUMS];
        int newCount = 0;
        
        for (int i = 0; i < sumCount; i++) {
            for (int j = 0; j < colSizes[r]; j++) {
                int newSum = possibleSums[i] + mat[r][j];
                // Add to newSums if not already present
                int found = 0;
                for (int k = 0; k < newCount; k++) {
                    if (newSums[k] == newSum) {
                        found = 1;
                        break;
                    }
                }
                if (!found && newCount < MAX_SUMS) {
                    newSums[newCount++] = newSum;
                }
            }
        }
        
        // Copy new sums back
        for (int i = 0; i < newCount; i++) {
            possibleSums[i] = newSums[i];
        }
        sumCount = newCount;
    }
    
    int minDiff = INT_MAX;
    for (int i = 0; i < sumCount; i++) {
        int diff = target - possibleSums[i];
        if (diff < 0) diff = -diff;
        if (diff < minDiff) minDiff = diff;
    }
    
    return minDiff;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int** mat = malloc(10 * sizeof(int*));
    int* colSizes = malloc(10 * sizeof(int));
    int rows = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            mat[rows] = malloc(10 * sizeof(int));
            int cols = 0;
            
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
                    mat[rows][cols++] = atoi(ptr);
                    while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
                } else {
                    ptr++;
                }
            }
            colSizes[rows] = cols;
            rows++;
        }
        ptr++;
    }
    
    int target;
    scanf("%d", &target);
    
    printf("%d\n", solution(mat, colSizes, rows, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n × S)

m rows, n elements per row, S possible sum values to track

✓ Linear Growth

Space Complexity

O(S)

Set to store all possible sum values, S can be large

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - Track Possible Sums — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler