What is the brute force approach and complexity for Find K Pairs with Smallest Sums?

List every pair, sort them by sum, and keep the first k with time complexity O(M · N log(M · N)) and space complexity O(M · N).

What is the optimal approach and complexity for Find K Pairs with Smallest Sums?

Min-heap of (i, j) pairs: start each row at j = 0, pop k times, push the next pair in the same row with optimal time complexity O(K log min(M, K)) and space complexity O(min(M, K)).

How do you identify the pattern for Find K Pairs with Smallest Sums?

Look for key signals in the prompt: "two sorted arrays" indicates Each fixed value from nums1 gives a sorted list of sums, so the problem is a merge of sorted lists.; "k smallest pairs" indicates Take out k times, in order. Stop there; do not sort the rest.; "pairs of values from two arrays" indicates One heap entry per row, and each row moves only to the right, which is why no duplicate pair can appear..

Find K Pairs with Smallest Sums

Medium·LeetCode #373 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

You get two integer arrays, nums1 and nums2, and both are sorted from smallest to largest. A pair takes one value from nums1 and one value from nums2. Its sum is the two values added together.

Return the k pairs with the smallest sums. Each pair must use a different combination of positions (one position in nums1, one in nums2). If there are fewer than k pairs in total, return all of them. The order of the answer does not matter.

Input

Two sorted integer arrays nums1 and nums2, and an integer k.

Output

A list of pairs [u, v] (u from nums1, v from nums2) with the smallest sums, at most k of them.

Example 1

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Output: [[1,2],[1,4],[1,6]]

The sums are 3, 5 and 7 for these three pairs. The next sum is 9, so these are the three smallest.

Example 2

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2

Output: [[1,1],[1,1]]

The two 1s in nums1 are different positions, so both pairs [1,1] count. Their sum is 2.

Constraints

• 1 ≤ nums1.length, nums2.length ≤ 10^5
• −10^9 ≤ nums1[i], nums2[i] ≤ 10^9
• nums1 and nums2 both are sorted in non-decreasing order
• 1 ≤ k ≤ 10^4
• k ≤ nums1.length · nums2.length

Pattern Recognition Clues

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

“two sorted arrays”

→ Each fixed value from nums1 gives a sorted list of sums, so the problem is a merge of sorted lists.

“k smallest pairs”

→ Take out k times, in order. Stop there; do not sort the rest.

“pairs of values from two arrays”

→ One heap entry per row, and each row moves only to the right, which is why no duplicate pair can appear.

Approach Complexity Ladder

Brute Force — all pairs, sort, take kO(M · N log(M · N))O(M · N)

List every pair, sort them by sum, and keep the first k

Better — max-heap of size k with an early stopO(M · N log K)O(K)

Scan the pairs, keep a max-heap of the k smallest sums, and skip the rest of a row once it is too big

Optimal — one heap entry per row, take k timesO(K log min(M, K))O(min(M, K))

Min-heap of (i, j) pairs: start each row at j = 0, pop k times, push the next pair in the same row

Brute Force Intuition

Build all m · n pairs, sort them by sum, and return the first k. Sorting every pair is wasteful when only k of them are needed.

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