# Find the Kth Smallest Sum of a Matrix With Sorted Rows
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows)
Canonical: https://scaleengineer.com/dsa/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Heap (Priority Queue), Matrix
---
## 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_.

**Example 1:**

**Input:** mat = [[1,3,11],[2,4,6]], k = 5
**Output:** 7
**Explanation:** Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.

**Example 2:**

**Input:** mat = [[1,3,11],[2,4,6]], k = 9
**Output:** 17

**Example 3:**

**Input:** mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
**Output:** 9
**Explanation:** Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.  

**Constraints:**

* `m == mat.length`
* `n == mat.length[i]`
* `1 <= m, n <= 40`
* `1 <= mat[i][j] <= 5000`
* `1 <= k <= min(200, nm)`
* `mat[i]` is a non-decreasing array.

# Approaches
## Brute Force Enumeration
The most straightforward approach is to generate every possible array sum. There are `m` rows and `n` choices in each row, leading to a total of `n^m` possible arrays. We can use a recursive backtracking function to explore all these combinations. As we form each complete array, we calculate its sum and store it in a list. After generating all possible sums, we sort the list and pick the `k`-th element (at index `k-1`).
**Time:** O(n^m * log(n^m)). It takes O(n^m) to generate all the sums, and then O(n^m * log(n^m)) to sort them. The sorting step dominates. · **Space:** O(n^m) to store all the generated sums in a list before sorting.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints.; Requires a large amount of memory to store all possible sums, which can lead to memory limit errors.
### Explanation
This method exhaustively enumerates all possibilities. A recursive function can traverse the matrix row by row. At each row, it branches out for every element in that row, adding it to the sum being built. When it reaches the end of the matrix (after picking one element from the last row), the accumulated sum is one of the possible array sums and is stored. Once all `n^m` sums are collected, sorting them allows us to find the `k`-th smallest one.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    List<Integer> allSums;
    int m, n;
    int[][] mat;

    public int kthSmallest(int[][] mat, int k) {
        this.allSums = new ArrayList<>();
        this.mat = mat;
        this.m = mat.length;
        this.n = mat[0].length;

        generateSums(0, 0);
        
        Collections.sort(allSums);
        
        return allSums.get(k - 1);
    }

    private void generateSums(int row, int currentSum) {
        if (row == m) {
            allSums.add(currentSum);
            return;
        }

        for (int j = 0; j < n; j++) {
            generateSums(row + 1, currentSum + mat[row][j]);
        }
    }
}
```
### Algorithm
*   Define a recursive function, say `generateSums(row, currentSum)`, that explores all possible combinations.
*   The function takes the current row index and the sum accumulated so far.
*   **Base Case:** If the `row` index reaches `m` (the number of rows), it means we have picked one element from each row. Add the `currentSum` to a global list of all possible sums.
*   **Recursive Step:** For the current `row`, iterate through each element `mat[row][j]`. Make a recursive call `generateSums(row + 1, currentSum + mat[row][j])` for each element.
*   Start the process by calling `generateSums(0, 0)`.
*   After the recursion completes, the list will contain all `n^m` possible sums.
*   Sort this list in non-decreasing order.
*   The `k`-th smallest sum is the element at index `k-1` in the sorted list.

## Iterative Merging with Sorting
Instead of generating all sums at once, we can build the list of smallest sums iteratively, row by row. We start with the elements of the first row as our initial set of sums. Then, for each subsequent row, we combine its elements with our current list of sums to generate a new set of sums. The crucial observation is that we only need to keep track of the `k` smallest sums at each step. So, after each row is processed, we sort the new sums and truncate the list to size `k`.
**Time:** O(m * k * n * log(k * n)). For each of the `m-1` merges, we generate `k*n` sums and sort them, which takes O(k*n * log(k*n)) time. · **Space:** O(k * n) to store the `newSums` list in each iteration.
**Pros:** Significantly more efficient than the brute-force approach.; Guaranteed to find the correct answer because the `k`-th smallest sum must be formed from sums that are themselves small.
**Cons:** Generates and sorts a potentially large intermediate list of size `k*n` at each step, which can be inefficient.; Higher space complexity compared to more optimized approaches.
### Explanation
This approach treats the problem as merging `m` sorted lists. We merge the list of sums from the first `i-1` rows with the `i`-th row. The size of the list of sums we maintain is capped at `k`. In each step, we combine every sum from the previous step with every element in the current row. This results in `k * n` new sums. We then sort this new list and keep the smallest `k` for the next iteration. This prevents the list of sums from growing exponentially.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int kthSmallest(int[][] mat, int k) {
        List<Integer> sums = new ArrayList<>();
        for (int num : mat[0]) {
            sums.add(num);
        }

        for (int i = 1; i < mat.length; i++) {
            List<Integer> newSums = new ArrayList<>();
            for (int prevSum : sums) {
                for (int currentNum : mat[i]) {
                    newSums.add(prevSum + currentNum);
                }
            }
            Collections.sort(newSums);
            sums = new ArrayList<>(newSums.subList(0, Math.min(k, newSums.size())));
        }

        return sums.get(k - 1);
    }
}
```
### Algorithm
*   Initialize a list, `sums`, with the elements from the first row, `mat[0]`.
*   Iterate through the matrix from the second row (`i = 1`) to the last row (`i = m-1`).
*   In each iteration, create a temporary list, `newSums`.
*   For each `prevSum` in the current `sums` list and for each `currentNum` in the current row `mat[i]`, add their sum (`prevSum + currentNum`) to `newSums`.
*   After populating `newSums` with all `sums.size() * n` combinations, sort `newSums`.
*   Trim `newSums` to keep only the first `k` elements, as any sum beyond the `k`-th smallest is unlikely to contribute to the final `k` smallest sums.
*   Update `sums` to be this new trimmed list.
*   After iterating through all rows, the `sums` list will hold the `k` smallest overall sums. The answer is the element at index `k-1`.

## Binary Search on the Answer
Since the problem asks for the `k`-th smallest value, and the possible sums are monotonic, we can use binary search on the answer. We define a range of possible sums and binary search for the smallest value `X` for which there are at least `k` array sums less than or equal to `X`. The main challenge is to efficiently count the number of array sums less than or equal to a given value `X`.
**Time:** O(log(Range) * CountComplexity), where `Range` is the difference between the maximum and minimum possible sums. The complexity of the counting function is hard to analyze tightly but is bounded by `O(k * n^m)` and is much faster in practice due to pruning. A loose practical bound might be `O(log(Range) * m * k)`. · **Space:** O(m) for the recursion stack depth of the DFS.
**Pros:** Very low space complexity, only requiring space for the recursion stack.; Can be faster than the sorting-based merge if the DFS pruning is effective.
**Cons:** The complexity of the DFS counting function is not trivial to analyze and can be slow in the worst case.; Implementation is more complex than the iterative merging approaches.
### Explanation
The counting function is the core of this approach. We can implement it with a recursive DFS function, `countLeq(target, row, currentSum)`. This function will find the number of ways to pick elements from `row` to `m-1` such that `currentSum` plus the sum of these elements does not exceed `target`. We can significantly optimize this search. Since rows are sorted, if `currentSum + mat[row][j]` already exceeds `target`, then `currentSum + mat[row][j+1]` will also exceed it, so we can prune the search. More importantly, we only care if the count is `>= k`. We can cap the returned count at `k`, which prunes the search tree dramatically.

```java
class Solution {
    int k;
    int m, n;
    int[][] mat;

    public int kthSmallest(int[][] mat, int k) {
        this.k = k;
        this.mat = mat;
        this.m = mat.length;
        this.n = mat[0].length;

        int low = 0;
        int high = 0;
        for (int i = 0; i < m; i++) {
            low += mat[i][0];
            high += mat[i][n - 1];
        }

        int ans = high;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            // Count sums <= mid
            int count = countLeq(mid, 0, 0);
            if (count >= k) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            } 
        }
        return ans;
    }

    private int countLeq(int targetSum, int r, int currentSum) {
        // Pruning: if current sum already exceeds target, no valid path forward.
        if (currentSum > targetSum) {
            return 0;
        }
        // Base case: successfully picked one element from each row.
        if (r == m) {
            return 1;
        }

        int count = 0;
        // Explore choices in the current row.
        for (int c = 0; c < n; c++) {
            count += countLeq(targetSum, r + 1, currentSum + mat[r][c]);
            // Capping: if we've already found k sums, no need to count further.
            if (count >= k) {
                return k;
            }
        }
        return count;
    }
}
```
### Algorithm
*   Determine the search range for the answer. The `low` bound is the sum of the first elements of each row. The `high` bound is the sum of the last elements of each row.
*   Perform a binary search on this range `[low, high]`.
*   For each `mid` value in the binary search, we need to count how many array sums are less than or equal to `mid`. Let's call this `count(mid)`.
*   The `count(mid)` function can be implemented using a depth-first search (DFS). `count(row, currentSum)` will count combinations from `row` onwards such that `currentSum +` (sum of elements from `row` to `m-1`) `<= mid`.
*   **DFS Optimization:** The count only needs to be accurate up to `k`. If at any point the number of sums found exceeds `k`, we can stop and return `k` (or `k+1`) to signal that we have found at least `k` sums. This is called capping.
*   If `count(mid) >= k`, it means the true `k`-th sum might be `mid` or something smaller. So we record `mid` as a potential answer and search in the lower half: `high = mid - 1`.
*   If `count(mid) < k`, the `k`-th sum must be larger than `mid`. We search in the upper half: `low = mid + 1`.
*   The last recorded potential answer will be the `k`-th smallest sum.

## Iterative Merging with a Min-Heap
This is the most efficient approach and is an optimization of the iterative merging strategy. Instead of generating all `k*n` sums and sorting them, we can find the `k` smallest sums at each merge step much more efficiently using a min-heap. When merging the list of `k` previous sums with a new row, we can find the `k` smallest new sums in `O(k * log k)` time. This is a classic application of heaps, similar to finding the `k`-th smallest element in a sorted matrix.
**Time:** O(m * k * log(k)). For each of the `m` rows, we perform a merge operation. The merge operation involves `k` pushes to initialize the heap and then `k` poll/push operations. Each heap operation takes `O(log k)` time. · **Space:** O(k) to store the min-heap and the list of the next `k` smallest sums.
**Pros:** Highly efficient time complexity.; Optimal space complexity among the valid approaches.
**Cons:** The logic is more complex to implement correctly compared to the sorting approach.
### Explanation
We process the matrix row by row. Let `prevSums` be the list of the `k` smallest sums using rows `0` to `i-1`. To get the `k` smallest sums for rows `0` to `i`, we need to find the `k` smallest values of `s + x` where `s` is in `prevSums` and `x` is in `mat[i]`. Since `prevSums` and `mat[i]` are sorted, we can use a min-heap. For each `s` in `prevSums`, the smallest possible new sum is `s + mat[i][0]`. We add all these initial candidates to a min-heap. Then, we repeatedly extract the minimum sum from the heap `k` times. When we extract a sum `s + mat[i][j]`, we add the next candidate, `s + mat[i][j+1]`, to the heap. This ensures we are always considering the smallest possible sums without generating all `k*n` combinations.

```java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int kthSmallest(int[][] mat, int k) {
        List<Integer> prevSums = new ArrayList<>();
        prevSums.add(0);

        for (int[] row : mat) {
            // Min-heap to find k smallest sums from prevSums and current row
            // Stores {sum, index_in_row}
            PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
            
            for (int sum : prevSums) {
                pq.offer(new int[]{sum + row[0], 0});
            }

            List<Integer> nextSums = new ArrayList<>();
            while (!pq.isEmpty() && nextSums.size() < k) {
                int[] top = pq.poll();
                int currentSum = top[0];
                int colIndex = top[1];
                
                nextSums.add(currentSum);
                
                if (colIndex + 1 < row.length) {
                    int prevSumComponent = currentSum - row[colIndex];
                    pq.offer(new int[]{prevSumComponent + row[colIndex + 1], colIndex + 1});
                }
            }
            prevSums = nextSums;
        }

        return prevSums.get(k - 1);
    }
}
```
### Algorithm
*   Initialize a list `sums` with a single element `0`. This represents the sum before considering any rows.
*   Iterate through each `row` in the matrix `mat`.
*   For each `row`, create a min-heap (PriorityQueue) to find the `k` smallest sums by combining `sums` from the previous step with the current `row`.
*   This subproblem is equivalent to finding the `k` smallest sums of pairs from two sorted lists (`sums` and `row`).
*   Initialize the min-heap: for each `s` in `sums`, push the pair `(s + row[0], 0)` onto the heap. The pair represents `(current_sum, index_in_row)`.
*   Create a `newSums` list. Extract up to `k` elements from the heap. For each element `(sum, index)` popped from the heap:
    *   Add `sum` to `newSums`.
    *   If `index + 1` is a valid index in the row, push a new pair to the heap: `(sum - row[index] + row[index+1], index + 1)`. This generates the next smallest sum candidate using the same element from the previous `sums` list.
*   After processing the heap, update `sums = newSums`.
*   After iterating through all rows, the final `sums` list contains the `k` smallest sums. The last element is the `k`-th smallest.

# Solutions
### Java

```java
class Solution {
public
  int kthSmallest(int[][] mat, int k) {
    int m = mat.length, n = mat[0].length;
    List<Integer> pre = new ArrayList<>(k);
    List<Integer> cur = new ArrayList<>(n * k);
    pre.add(0);
    for (int[] row : mat) {
      cur.clear();
      for (int a : pre) {
        for (int b : row) {
          cur.add(a + b);
        }
      }
      Collections.sort(cur);
      pre.clear();
      for (int i = 0; i < Math.min(k, cur.size()); ++i) {
        pre.add(cur.get(i));
      }
    }
    return pre.get(k - 1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int kthSmallest(vector<vector<int>> &mat, int k) {
    int pre[k];
    int cur[mat[0].size() * k];
    memset(pre, 0, sizeof pre);
    int size = 1;
    for (auto &row : mat) {
      int i = 0;
      for (int j = 0; j < size; ++j) {
        for (int &v : row) {
          cur[i++] = pre[j] + v;
        }
      }
      sort(cur, cur + i);
      size = min(i, k);
      for (int j = 0; j < size; ++j) {
        pre[j] = cur[j];
      }
    }
    return pre[k - 1];
  }
};

```

### Python

```python
class Solution:
    def kthSmallest(self, mat: List[List[int]], k: int) -> int: pre = [0] for cur in mat: pre = sorted(a + b for a in pre for b in cur[: k])[: k] return pre[- 1]

```