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

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

✓ Memoization

⏱️ Time: N/A Space: N/A

Dp 2d

⏱️ Time: N/A Space: N/A

Binary Search on Answer Space

⏱️ Time: O(log(sum_range) × m × n^m) Space: O(m)

Instead of generating sums explicitly, binary search on the answer space. For each candidate answer, count how many array sums are less than or equal to it using DFS or combinatorial counting.

Brute Force - Generate All Combinations

⏱️ Time: O(n^m × log(n^m)) Space: O(n^m)

Create all possible combinations by choosing one element from each row, calculate their sums, sort them, and return the kth element. This explores the entire solution space.

Priority Queue (Min-Heap) Approach

⏱️ Time: O(k × log(k) × m) Space: O(k)

Start with the smallest possible sum (first element from each row) and use a priority queue to systematically explore the next smallest sums. This avoids generating all combinations upfront.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

#define MAX_HEAP_SIZE 100000
#define MAX_VISITED 50000
#define MAX_ROWS 100
#define MAX_COLS 100
#define MAX_LINE 10000

typedef struct {
    int sum;
    int indices[MAX_ROWS];
    int m;
} State;

typedef struct {
    State data[MAX_HEAP_SIZE];
    int size;
} MinHeap;

typedef struct {
    char keys[MAX_VISITED][200];
    int size;
} VisitedSet;

int mat[MAX_ROWS][MAX_COLS];
int matRows, matCols;
MinHeap heap;
VisitedSet visited;

void heapify(int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    
    if (left < heap.size && heap.data[left].sum < heap.data[smallest].sum)
        smallest = left;
    
    if (right < heap.size && heap.data[right].sum < heap.data[smallest].sum)
        smallest = right;
    
    if (smallest != idx) {
        State temp = heap.data[idx];
        heap.data[idx] = heap.data[smallest];
        heap.data[smallest] = temp;
        heapify(smallest);
    }
}

void heapPush(State state) {
    heap.data[heap.size] = state;
    int i = heap.size;
    heap.size++;
    
    while (i > 0 && heap.data[(i-1)/2].sum > heap.data[i].sum) {
        State temp = heap.data[i];
        heap.data[i] = heap.data[(i-1)/2];
        heap.data[(i-1)/2] = temp;
        i = (i-1)/2;
    }
}

State heapPop() {
    State result = heap.data[0];
    heap.data[0] = heap.data[heap.size-1];
    heap.size--;
    heapify(0);
    return result;
}

void indicesToString(int* indices, int m, char* result) {
    result[0] = '\0';
    for (int i = 0; i < m; i++) {
        char temp[20];
        sprintf(temp, "%d", indices[i]);
        strcat(result, temp);
        if (i < m-1) strcat(result, ",");
    }
}

bool isVisited(char* key) {
    for (int i = 0; i < visited.size; i++) {
        if (strcmp(visited.keys[i], key) == 0)
            return true;
    }
    return false;
}

void addVisited(char* key) {
    if (visited.size < MAX_VISITED) {
        strcpy(visited.keys[visited.size], key);
        visited.size++;
    }
}

void parseMatrix(char* line) {
    // Simple parsing for matrix format [[a,b,c],[d,e,f]]
    matRows = 0;
    matCols = 0;
    
    int i = 1; // Skip first '['
    while (line[i] && line[i] != '\n') {
        if (line[i] == '[') {
            i++;
            matCols = 0;
            int num = 0;
            bool inNumber = false;
            
            while (line[i] && line[i] != ']') {
                if (line[i] >= '0' && line[i] <= '9') {
                    num = num * 10 + (line[i] - '0');
                    inNumber = true;
                } else if (line[i] == ',' || line[i] == ']') {
                    if (inNumber) {
                        mat[matRows][matCols] = num;
                        matCols++;
                        num = 0;
                        inNumber = false;
                    }
                }
                i++;
            }
            if (inNumber) {
                mat[matRows][matCols] = num;
                matCols++;
            }
            matRows++;
        }
        i++;
    }
}

int kthSmallest(int k) {
    heap.size = 0;
    visited.size = 0;
    
    // Start with the first element from each row
    State initial;
    initial.sum = 0;
    initial.m = matRows;
    for (int i = 0; i < matRows; i++) {
        initial.indices[i] = 0;
        initial.sum += mat[i][0];
    }
    
    heapPush(initial);
    char key[200];
    indicesToString(initial.indices, matRows, key);
    addVisited(key);
    
    for (int count = 1; count < k; count++) {
        State current = heapPop();
        
        // Generate next states by incrementing each index
        for (int i = 0; i < matRows; i++) {
            if (current.indices[i] + 1 < matCols) {
                State newState = current;
                newState.indices[i]++;
                
                indicesToString(newState.indices, matRows, key);
                if (!isVisited(key)) {
                    newState.sum = current.sum - mat[i][current.indices[i]] + mat[i][newState.indices[i]];
                    heapPush(newState);
                    addVisited(key);
                }
            }
        }
    }
    
    return heap.data[0].sum;
}

int main() {
    char line[MAX_LINE];
    fgets(line, MAX_LINE, stdin);
    parseMatrix(line);
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", kthSmallest(k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear 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