Find the Kth Smallest Sum of a Matrix With Sorted Rows

Find the Kth Smallest Sum of a Matrix With Sorted Rows - Problem

You are given an m x n matrix mat that has its rows sorted in non-decreasing order and an integer k.

You are allowed to choose exactly one element from each row to form an array.

Return the kth smallest array sum among all possible arrays.

Input & Output

Example 1 — Basic Case

$ Input: mat = [[1,3,11],[2,4,6]], k = 5

› Output: 7

💡 Note: All possible sums: [3,5,7,5,7,9,13,15,17]. Sorted: [3,5,5,7,7,9,13,15,17]. The 5th smallest is 7.

Example 2 — Small k

$ Input: mat = [[1,3,11],[2,4,6]], k = 1

› Output: 3

💡 Note: The smallest possible sum is choosing the first element from each row: 1 + 2 = 3.

Example 3 — Single Row

$ Input: mat = [[1,10,10,10,10]], k = 3

› Output: 10

💡 Note: Only one row, so we can only choose one element. All sums after the first are 10, so k=3 gives 10.

Constraints

m == mat.length
n == mat[i].length
1 ≤ m, n ≤ 40
1 ≤ mat[i][j] ≤ 5000
1 ≤ k ≤ min(200, n^m)

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Each row is sorted in non-decreasing order

Generate Arrays

Choose exactly one element from each row

Find Kth Sum

Return the kth smallest array sum

Key Takeaway

🎯 Key Insight: Use a min-heap to generate sums in ascending order without creating all combinations

Asked in

G Google 15 f Facebook 12 a Amazon 8

This problem requires finding the kth smallest sum from all possible arrays formed by choosing one element from each row. The key insight is using a min-heap to generate sums in ascending order without creating all combinations upfront. Best approach uses priority queue with state tracking. Time: O(k × log k × m), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Combinations	O(n^m × log(n^m))	O(n^m)	Generate all possible array sums and sort to find the kth smallest
Binary Search on Answer Space	O(log(sum_range) × m × n^m)	O(m)	Binary search on possible sum values and count how many sums are smaller
Priority Queue (Min-Heap) Approach	O(k × log(k) × m)	O(k)	Use a min-heap to generate array sums in ascending order

Brute Force - Generate All Combinations — Algorithm Steps

Generate all possible combinations using recursion
Calculate sum for each combination
Sort all sums and return kth element

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All

Create all possible combinations

Calculate Sums

Sum each combination

Sort & Pick

Sort and return kth element

Code -

solution.c — C

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

void generateSums(int** mat, int* colSizes, int rows, int row, int currentSum, int* sums, int* sumCount) {
    if (row == rows) {
        sums[(*sumCount)++] = currentSum;
        return;
    }
    
    for (int col = 0; col < colSizes[row]; col++) {
        generateSums(mat, colSizes, rows, row + 1, currentSum + mat[row][col], sums, sumCount);
    }
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int** mat, int* colSizes, int rows, int k) {
    int maxSums = 1;
    for (int i = 0; i < rows; i++) {
        maxSums *= colSizes[i];
    }
    
    int* sums = (int*)malloc(maxSums * sizeof(int));
    int sumCount = 0;
    
    generateSums(mat, colSizes, rows, 0, 0, sums, &sumCount);
    qsort(sums, sumCount, sizeof(int), compare);
    
    int result = sums[k - 1];
    free(sums);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for demo - in practice would need robust JSON parser
    int** mat = (int**)malloc(100 * sizeof(int*));
    int* colSizes = (int*)malloc(100 * sizeof(int));
    int rows = 0;
    
    // For demo, assume 2x3 matrix [[1,3,11],[2,4,6]]
    mat[0] = (int*)malloc(3 * sizeof(int));
    mat[0][0] = 1; mat[0][1] = 3; mat[0][2] = 11;
    colSizes[0] = 3;
    
    mat[1] = (int*)malloc(3 * sizeof(int));
    mat[1][0] = 2; mat[1][1] = 4; mat[1][2] = 6;
    colSizes[1] = 3;
    
    rows = 2;
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(mat, colSizes, rows, k));
    
    for (int i = 0; i < rows; i++) {
        free(mat[i]);
    }
    free(mat);
    free(colSizes);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^m × log(n^m))

Generate n^m combinations and sort them

⚡ Linearithmic

Space Complexity

O(n^m)

Store all possible sums in memory

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

780 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

Brute Force - Generate All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler