What is the brute force approach and complexity for Find the Kth Smallest Sum of a Matrix With Sorted Rows?

Build all n^m sums, sort them, and read position k with time complexity O(n^m · log(n^m)) and space complexity O(n^m).

What is the optimal approach and complexity for Find the Kth Smallest Sum of a Matrix With Sorted Rows?

Merge the kept sums with each next row using the heap from the k smallest pair sums question with optimal time complexity O(M · K log K) and space complexity O(K).

Find the Kth Smallest Sum of a Matrix With Sorted Rows

Q: How do you identify the pattern for Find the Kth Smallest Sum of a Matrix With Sorted Rows?

Look for key signals in the prompt: "one number from each row" indicates Each sum merges m sorted lists, one value from each. Merge them one pair at a time.; "k-th smallest sum" indicates Keep only k partial sums. Anything beyond that can never reach the top k.; "rows are sorted" indicates Two sorted lists can be merged with the k-smallest-pairs heap from Find K Pairs with Smallest Sums, the second question in this group..

Hard·LeetCode #1439 Pro OnlyInterview-Level

LeetCode

Problem Statement

You get an m × n matrix mat. Every row is sorted from smallest to largest.

Pick exactly one number from each row. Add the picked numbers together to get one sum. With m rows there are n^m ways to pick, so there are that many sums (repeats count separately).

Return the k-th smallest of all those sums.

Input

An m × n integer matrix mat whose rows are sorted, and an integer k.

Output

One integer: the k-th smallest sum over all ways to pick one number from each row.

Example 1

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

Output: 7

The nine sums are 3, 5, 7, 5, 7, 9, 13, 15, 17. Sorted, they are 3, 5, 5, 7, 7, 9, 13, 15, 17. The 5th is 7.

Example 2

Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7

Output: 9

The seven smallest sums are 4, 5, 7, 8, 8, 8 and 9. The 7th is 9.

Constraints

• m == mat.length
• n == mat[i].length
• 1 ≤ m, n ≤ 40
• 1 ≤ mat[i][j] ≤ 5000
• 1 ≤ k ≤ min(200, n^m)
• mat[i] is a non-decreasing array

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“one number from each row”

→ Each sum merges m sorted lists, one value from each. Merge them one pair at a time.

“k-th smallest sum”

→ Keep only k partial sums. Anything beyond that can never reach the top k.

“rows are sorted”

→ Two sorted lists can be merged with the k-smallest-pairs heap from Find K Pairs with Smallest Sums, the second question in this group.

Approach Complexity Ladder

Brute Force — every choice, sort, read kO(n^m · log(n^m))O(n^m)

Build all n^m sums, sort them, and read position k

Better — merge one row at a time, keep k sumsO(M · K·N log(K·N))O(K·N)

Start from row 0; for each next row, add its numbers to the kept sums, sort, and keep the first k

Optimal — merge pairs with the k-smallest-pairs heapO(M · K log K)O(K)

Merge the kept sums with each next row using the heap from the k smallest pair sums question

Brute Force Intuition

Build all n^m sums one row at a time, sort them, and read position k − 1. There are n^m choices, so this only works for tiny matrices.

Recognition rule for this sub-pattern:

Pop K times from the merged stream; the Kth pop is the answer.

Remember this · K-way Merge

Trigger

K sorted lists/arrays, kth smallest across sorted rows, smallest range covering all lists.

Think

The next smallest item overall must be the front of some list — which one?

Key question

What do I push back into the heap after popping?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like K-way Merge translate into production architectures and low-level memory mechanics.

LLD Architecture