Kth Smallest Sum in Two Sorted Arrays

🎯

Kth Smallest Sum in Two Sorted Arrays

hardHEAPAmazonGoogle

Imagine you have two sorted price lists from two different suppliers, and you want to find the k-th cheapest combined purchase you can make by buying one item from each supplier.

💡 This problem involves combining two sorted arrays to find the k-th smallest sum of pairs. Beginners often struggle because the naive approach of generating all pairs is too slow, and understanding how to efficiently explore pairs using a heap and a visited set is non-trivial.

📋

Problem Statement

Given two sorted arrays nums1 and nums2, find the k-th smallest sum of a pair (nums1[i] + nums2[j]) where 0 ≤ i < len(nums1) and 0 ≤ j < len(nums2). Return the sum value.

1 ≤ len(nums1), len(nums2) ≤ 10^51 ≤ k ≤ len(nums1) * len(nums2)-10^9 ≤ nums1[i], nums2[j] ≤ 10^9nums1 and nums2 are sorted in ascending order

💡

Example

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

Output7

The pairs sorted by sum are (1+2=3), (1+4=5), (1+6=7), (7+2=9), (7+4=11), (11+2=13), ... The 3rd smallest sum is 7.

• k = 1 → smallest sum is nums1[0] + nums2[0]
• k = len(nums1)*len(nums2) → largest possible sum
• nums1 or nums2 contains negative numbers → sums can be negative
• nums1 or nums2 contains duplicates → sums may repeat

⚠️

Common Mistakes

Not using a visited set in heap approach

Duplicate pairs pushed into heap causing incorrect counts and TLE

✅ Maintain a visited set to track pushed pairs

Incorrect indexing when pushing next pairs (i+1,j) and (i,j+1)

Index out of bounds errors or missing valid pairs

✅ Check bounds before pushing pairs

Using brute force for large inputs

Time limit exceeded or memory overflow

✅ Explain brute force only, then implement heap or binary search approach

In binary search approach, counting pairs incorrectly

Wrong count leads to incorrect binary search results

✅ Use two pointers carefully to count pairs ≤ mid

Not handling negative numbers correctly

Incorrect sum ranges or counts

✅ Initialize low and high using actual min and max sums

🧠

Brute Force (Generate All Pairs and Sort)

💡 This approach exists to establish a baseline understanding by brute forcing all possible pairs. It is simple but inefficient, helping beginners grasp the problem's combinatorial nature.

Intuition

Generate all possible sums from pairs of elements in nums1 and nums2, then sort them to find the k-th smallest sum.

Algorithm

1. Initialize an empty list to store all sums.
2. Use nested loops to generate sums of every pair (nums1[i] + nums2[j]).
3. Sort the list of sums in ascending order.
4. Return the element at index k-1.

💡 The nested loops create all pairs explicitly, which is easy to understand but leads to large time and space usage.

</>

Code

def kthSmallestSum(nums1, nums2, k):
    sums = []
    for i in range(len(nums1)):
        for j in range(len(nums2)):
            sums.append(nums1[i] + nums2[j])
    sums.sort()
    return sums[k-1]

# Driver code
if __name__ == '__main__':
    nums1 = [1,7,11]
    nums2 = [2,4,6]
    k = 3
    print(kthSmallestSum(nums1, nums2, k))  # Output: 7

Line Notes

sums = []Initialize list to store all pair sums

for i in range(len(nums1))Outer loop to iterate over nums1 elements

for j in range(len(nums2))Inner loop to iterate over nums2 elements for each nums1[i]

sums.append(nums1[i] + nums2[j])Calculate and store sum of current pair

sums.sort()Sort all sums to find the k-th smallest

return sums[k-1]Return the k-th smallest sum (1-based indexing)

import java.util.*;
public class KthSmallestSum {
    public static int kthSmallestSum(int[] nums1, int[] nums2, int k) {
        List<Integer> sums = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                sums.add(nums1[i] + nums2[j]);
            }
        }
        Collections.sort(sums);
        return sums.get(k - 1);
    }

    public static void main(String[] args) {
        int[] nums1 = {1,7,11};
        int[] nums2 = {2,4,6};
        int k = 3;
        System.out.println(kthSmallestSum(nums1, nums2, k)); // Output: 7
    }
}

Line Notes

List<Integer> sums = new ArrayList<>()Create list to hold all sums

for (int i = 0; i < nums1.length; i++)Outer loop over nums1

for (int j = 0; j < nums2.length; j++)Inner loop over nums2 for each nums1[i]

sums.add(nums1[i] + nums2[j])Add sum of current pair to list

Collections.sort(sums)Sort sums to find k-th smallest

return sums.get(k - 1)Return the k-th smallest sum

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int kthSmallestSum(vector<int>& nums1, vector<int>& nums2, int k) {
    vector<int> sums;
    for (int i = 0; i < nums1.size(); i++) {
        for (int j = 0; j < nums2.size(); j++) {
            sums.push_back(nums1[i] + nums2[j]);
        }
    }
    sort(sums.begin(), sums.end());
    return sums[k - 1];
}

int main() {
    vector<int> nums1 = {1,7,11};
    vector<int> nums2 = {2,4,6};
    int k = 3;
    cout << kthSmallestSum(nums1, nums2, k) << endl; // Output: 7
    return 0;
}

Line Notes

vector<int> sums;Vector to store all pair sums

for (int i = 0; i < nums1.size(); i++)Outer loop over nums1 elements

for (int j = 0; j < nums2.size(); j++)Inner loop over nums2 elements

sums.push_back(nums1[i] + nums2[j]);Add sum of current pair

sort(sums.begin(), sums.end());Sort sums to find k-th smallest

return sums[k - 1];Return the k-th smallest sum

function kthSmallestSum(nums1, nums2, k) {
    const sums = [];
    for (let i = 0; i < nums1.length; i++) {
        for (let j = 0; j < nums2.length; j++) {
            sums.push(nums1[i] + nums2[j]);
        }
    }
    sums.sort((a, b) => a - b);
    return sums[k - 1];
}

// Test
const nums1 = [1,7,11];
const nums2 = [2,4,6];
const k = 3;
console.log(kthSmallestSum(nums1, nums2, k)); // Output: 7

Line Notes

const sums = []Initialize array to hold all sums

for (let i = 0; i < nums1.length; i++)Outer loop over nums1

for (let j = 0; j < nums2.length; j++)Inner loop over nums2

sums.push(nums1[i] + nums2[j])Add sum of current pair

sums.sort((a, b) => a - b)Sort sums ascending to find k-th smallest

return sums[k - 1]Return the k-th smallest sum

⏱

Complexity

TimeO(n*m log(n*m)) where n and m are lengths of nums1 and nums2

SpaceO(n*m) to store all pair sums

We generate all n*m pairs and then sort them, which dominates the runtime and memory.

💡 For arrays of size 1000 each, this means 1,000,000 sums and sorting them, which is very slow and memory-heavy.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Min-Heap with Pair Expansion and Visited Set

💡 This approach improves efficiency by using a min-heap to explore sums in ascending order without generating all pairs, teaching how to prune search space smartly.

Intuition

Start with the smallest pair sum (nums1[0] + nums2[0]) in a min-heap. Repeatedly extract the smallest sum and push the next possible pairs by incrementing indices, avoiding duplicates with a visited set.

Algorithm

1. Initialize a min-heap and a visited set.
2. Push the pair (0,0) with sum nums1[0] + nums2[0] into the heap and mark visited.
3. Repeat k times: pop the smallest sum from the heap.
4. For the popped pair (i,j), push pairs (i+1,j) and (i,j+1) if not visited.
5. After k pops, the last popped sum is the answer.

💡 The heap ensures we always pick the next smallest sum, and the visited set prevents revisiting pairs, making the search efficient.

</>

Code

import heapq

def kthSmallestSum(nums1, nums2, k):
    n, m = len(nums1), len(nums2)
    min_heap = []
    visited = set()
    heapq.heappush(min_heap, (nums1[0] + nums2[0], 0, 0))
    visited.add((0, 0))

    for _ in range(k):
        sum_val, i, j = heapq.heappop(min_heap)
        if i + 1 < n and (i + 1, j) not in visited:
            heapq.heappush(min_heap, (nums1[i + 1] + nums2[j], i + 1, j))
            visited.add((i + 1, j))
        if j + 1 < m and (i, j + 1) not in visited:
            heapq.heappush(min_heap, (nums1[i] + nums2[j + 1], i, j + 1))
            visited.add((i, j + 1))
    return sum_val

# Driver code
if __name__ == '__main__':
    nums1 = [1,7,11]
    nums2 = [2,4,6]
    k = 3
    print(kthSmallestSum(nums1, nums2, k))  # Output: 7

Line Notes

import heapqImport heapq for efficient min-heap operations

min_heap = []Initialize min-heap to store sums with indices

visited = set()Track visited pairs to avoid duplicates

heapq.heappush(min_heap, (nums1[0] + nums2[0], 0, 0))Push initial smallest sum pair

for _ in range(k)Extract k times to find k-th smallest sum

heapq.heappop(min_heap)Pop smallest sum from heap

if i + 1 < n and (i + 1, j) not in visitedPush next pair by incrementing i if unvisited

if j + 1 < m and (i, j + 1) not in visitedPush next pair by incrementing j if unvisited

return sum_valReturn the k-th smallest sum after k pops

import java.util.*;

public class KthSmallestSum {
    static class Pair implements Comparable<Pair> {
        int sum, i, j;
        Pair(int sum, int i, int j) {
            this.sum = sum;
            this.i = i;
            this.j = j;
        }
        public int compareTo(Pair other) {
            return this.sum - other.sum;
        }
    }

    public static int kthSmallestSum(int[] nums1, int[] nums2, int k) {
        int n = nums1.length, m = nums2.length;
        PriorityQueue<Pair> minHeap = new PriorityQueue<>();
        Set<String> visited = new HashSet<>();
        minHeap.offer(new Pair(nums1[0] + nums2[0], 0, 0));
        visited.add("0,0");

        int sumVal = 0;
        for (int count = 0; count < k; count++) {
            Pair curr = minHeap.poll();
            sumVal = curr.sum;
            int i = curr.i, j = curr.j;
            if (i + 1 < n && !visited.contains((i + 1) + "," + j)) {
                minHeap.offer(new Pair(nums1[i + 1] + nums2[j], i + 1, j));
                visited.add((i + 1) + "," + j);
            }
            if (j + 1 < m && !visited.contains(i + "," + (j + 1))) {
                minHeap.offer(new Pair(nums1[i] + nums2[j + 1], i, j + 1));
                visited.add(i + "," + (j + 1));
            }
        }
        return sumVal;
    }

    public static void main(String[] args) {
        int[] nums1 = {1,7,11};
        int[] nums2 = {2,4,6};
        int k = 3;
        System.out.println(kthSmallestSum(nums1, nums2, k)); // Output: 7
    }
}

Line Notes

static class Pair implements Comparable<Pair>Define Pair class to store sum and indices with ordering

PriorityQueue<Pair> minHeap = new PriorityQueue<>()Min-heap to get smallest sum pairs

Set<String> visited = new HashSet<>()Track visited pairs as strings to avoid duplicates

minHeap.offer(new Pair(nums1[0] + nums2[0], 0, 0))Add initial smallest sum pair

for (int count = 0; count < k; count++)Extract k times to find k-th smallest sum

Pair curr = minHeap.poll()Pop smallest sum pair

if (i + 1 < n && !visited.contains(...))Add next pair by incrementing i if unvisited

if (j + 1 < m && !visited.contains(...))Add next pair by incrementing j if unvisited

return sumValReturn the k-th smallest sum after k pops

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

struct Pair {
    int sum, i, j;
    Pair(int s, int x, int y) : sum(s), i(x), j(y) {}
    bool operator>(const Pair& other) const {
        return sum > other.sum;
    }
};

int kthSmallestSum(vector<int>& nums1, vector<int>& nums2, int k) {
    int n = nums1.size(), m = nums2.size();
    priority_queue<Pair, vector<Pair>, greater<Pair>> minHeap;
    set<pair<int,int>> visited;
    minHeap.emplace(nums1[0] + nums2[0], 0, 0);
    visited.insert({0, 0});

    int sumVal = 0;
    for (int count = 0; count < k; count++) {
        Pair curr = minHeap.top();
        minHeap.pop();
        sumVal = curr.sum;
        int i = curr.i, j = curr.j;
        if (i + 1 < n && visited.find({i + 1, j}) == visited.end()) {
            minHeap.emplace(nums1[i + 1] + nums2[j], i + 1, j);
            visited.insert({i + 1, j});
        }
        if (j + 1 < m && visited.find({i, j + 1}) == visited.end()) {
            minHeap.emplace(nums1[i] + nums2[j + 1], i, j + 1);
            visited.insert({i, j + 1});
        }
    }
    return sumVal;
}

int main() {
    vector<int> nums1 = {1,7,11};
    vector<int> nums2 = {2,4,6};
    int k = 3;
    cout << kthSmallestSum(nums1, nums2, k) << endl; // Output: 7
    return 0;
}

Line Notes

struct PairStruct to hold sum and indices with comparison operator

priority_queue<Pair, vector<Pair>, greater<Pair>> minHeapMin-heap for smallest sums

set<pair<int,int>> visitedSet to track visited pairs

minHeap.emplace(nums1[0] + nums2[0], 0, 0)Push initial smallest sum pair

for (int count = 0; count < k; count++)Extract k times to find k-th smallest sum

Pair curr = minHeap.top(); minHeap.pop();Pop smallest sum pair

if (i + 1 < n && visited.find(...) == visited.end())Add next pair by incrementing i if unvisited

if (j + 1 < m && visited.find(...) == visited.end())Add next pair by incrementing j if unvisited

return sumValReturn the k-th smallest sum

class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent][0] <= this.heap[idx][0]) break;
            this.swap(parent, idx);
            idx = parent;
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return top;
    }
    bubbleDown() {
        let idx = 0;
        const length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let smallest = idx;
            if (left < length && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
            if (right < length && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
            if (smallest === idx) break;
            this.swap(idx, smallest);
            idx = smallest;
        }
    }
    size() {
        return this.heap.length;
    }
}

function kthSmallestSum(nums1, nums2, k) {
    const n = nums1.length, m = nums2.length;
    const minHeap = new MinHeap();
    const visited = new Set();
    minHeap.push([nums1[0] + nums2[0], 0, 0]);
    visited.add('0,0');

    let sumVal = 0;
    for (let count = 0; count < k; count++) {
        const [sum, i, j] = minHeap.pop();
        sumVal = sum;
        if (i + 1 < n && !visited.has(`${i + 1},${j}`)) {
            minHeap.push([nums1[i + 1] + nums2[j], i + 1, j]);
            visited.add(`${i + 1},${j}`);
        }
        if (j + 1 < m && !visited.has(`${i},${j + 1}`)) {
            minHeap.push([nums1[i] + nums2[j + 1], i, j + 1]);
            visited.add(`${i},${j + 1}`);
        }
    }
    return sumVal;
}

// Test
const nums1 = [1,7,11];
const nums2 = [2,4,6];
const k = 3;
console.log(kthSmallestSum(nums1, nums2, k)); // Output: 7

Line Notes

class MinHeapCustom min-heap implementation for priority queue

minHeap.push([nums1[0] + nums2[0], 0, 0])Push initial smallest sum pair

const visited = new Set()Track visited pairs to avoid duplicates

for (let count = 0; count < k; count++)Extract k times to find k-th smallest sum

const [sum, i, j] = minHeap.pop()Pop smallest sum pair

if (i + 1 < n && !visited.has(...))Add next pair by incrementing i if unvisited

if (j + 1 < m && !visited.has(...))Add next pair by incrementing j if unvisited

return sumValReturn the k-th smallest sum

⏱

Complexity

TimeO(k log k)

SpaceO(k)

We push at most k pairs into the heap, each heap operation costs O(log k). Visited set prevents duplicates.

💡 For k=1000, this means roughly 1000 log 1000 ≈ 10,000 operations, which is efficient for large arrays.

Interview Verdict: Accepted

This approach is optimal and accepted for large inputs, demonstrating efficient use of heaps and pruning.

🧠

Binary Search on Sum Range with Counting

💡 This approach uses binary search on the possible sum values to find the k-th smallest sum, teaching how to combine binary search with counting pairs efficiently.

Intuition

The smallest sum is nums1[0] + nums2[0], and the largest sum is nums1[-1] + nums2[-1]. Use binary search on this range to guess a sum mid, count how many pairs have sums ≤ mid, and adjust search accordingly.

Algorithm

1. Set low = nums1[0] + nums2[0], high = nums1[-1] + nums2[-1].
2. While low < high:
3. Compute mid = (low + high) // 2.
4. Count pairs with sum ≤ mid using two pointers.
5. If count < k, set low = mid + 1; else high = mid.
6. Return low as the k-th smallest sum.

💡 Binary search narrows the sum range, and counting pairs efficiently avoids enumerating all pairs.

</>

Code

def countPairs(nums1, nums2, mid):
    count = 0
    j = len(nums2) - 1
    for i in range(len(nums1)):
        while j >= 0 and nums1[i] + nums2[j] > mid:
            j -= 1
        count += (j + 1)
    return count

def kthSmallestSum(nums1, nums2, k):
    low = nums1[0] + nums2[0]
    high = nums1[-1] + nums2[-1]
    while low < high:
        mid = (low + high) // 2
        if countPairs(nums1, nums2, mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

# Driver code
if __name__ == '__main__':
    nums1 = [1,7,11]
    nums2 = [2,4,6]
    k = 3
    print(kthSmallestSum(nums1, nums2, k))  # Output: 7

Line Notes

def countPairs(nums1, nums2, mid)Helper to count pairs with sum ≤ mid

j = len(nums2) - 1Start pointer j at end of nums2

while j >= 0 and nums1[i] + nums2[j] > midMove j left to find valid pairs for nums1[i]

count += (j + 1)Add number of valid pairs for current i

low = nums1[0] + nums2[0]Initialize low bound of sum range

high = nums1[-1] + nums2[-1]Initialize high bound of sum range

while low < highBinary search loop

if countPairs(...) < kIf fewer than k pairs ≤ mid, increase low

else: high = midOtherwise, decrease high

return lowReturn k-th smallest sum

public class KthSmallestSum {
    public static int countPairs(int[] nums1, int[] nums2, int mid) {
        int count = 0, j = nums2.length - 1;
        for (int i = 0; i < nums1.length; i++) {
            while (j >= 0 && nums1[i] + nums2[j] > mid) j--;
            count += (j + 1);
        }
        return count;
    }

    public static int kthSmallestSum(int[] nums1, int[] nums2, int k) {
        int low = nums1[0] + nums2[0];
        int high = nums1[nums1.length - 1] + nums2[nums2.length - 1];
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countPairs(nums1, nums2, mid) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums1 = {1,7,11};
        int[] nums2 = {2,4,6};
        int k = 3;
        System.out.println(kthSmallestSum(nums1, nums2, k)); // Output: 7
    }
}

Line Notes

int j = nums2.length - 1Pointer j starts at end of nums2

while (j >= 0 && nums1[i] + nums2[j] > mid)Move j left to find valid pairs for nums1[i]

count += (j + 1)Add count of valid pairs for current i

int low = nums1[0] + nums2[0]Initialize low bound

int high = nums1[nums1.length - 1] + nums2[nums2.length - 1]Initialize high bound

while (low < high)Binary search loop

if (countPairs(...) < k)Adjust low if fewer pairs ≤ mid

else { high = mid; }Adjust high otherwise

return lowReturn k-th smallest sum

#include <iostream>
#include <vector>
using namespace std;

int countPairs(const vector<int>& nums1, const vector<int>& nums2, int mid) {
    int count = 0, j = (int)nums2.size() - 1;
    for (int i = 0; i < (int)nums1.size(); i++) {
        while (j >= 0 && nums1[i] + nums2[j] > mid) j--;
        count += (j + 1);
    }
    return count;
}

int kthSmallestSum(const vector<int>& nums1, const vector<int>& nums2, int k) {
    int low = nums1[0] + nums2[0];
    int high = nums1.back() + nums2.back();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (countPairs(nums1, nums2, mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    vector<int> nums1 = {1,7,11};
    vector<int> nums2 = {2,4,6};
    int k = 3;
    cout << kthSmallestSum(nums1, nums2, k) << endl; // Output: 7
    return 0;
}

Line Notes

int j = (int)nums2.size() - 1Pointer j starts at end of nums2

while (j >= 0 && nums1[i] + nums2[j] > mid) j--Move j left to find valid pairs

count += (j + 1)Add count of valid pairs for current i

int low = nums1[0] + nums2[0]Initialize low bound

int high = nums1.back() + nums2.back()Initialize high bound

while (low < high)Binary search loop

if (countPairs(...) < k)Adjust low if fewer pairs ≤ mid

else { high = mid; }Adjust high otherwise

return lowReturn k-th smallest sum

function countPairs(nums1, nums2, mid) {
    let count = 0;
    let j = nums2.length - 1;
    for (let i = 0; i < nums1.length; i++) {
        while (j >= 0 && nums1[i] + nums2[j] > mid) {
            j--;
        }
        count += (j + 1);
    }
    return count;
}

function kthSmallestSum(nums1, nums2, k) {
    let low = nums1[0] + nums2[0];
    let high = nums1[nums1.length - 1] + nums2[nums2.length - 1];
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (countPairs(nums1, nums2, mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

// Test
const nums1 = [1,7,11];
const nums2 = [2,4,6];
const k = 3;
console.log(kthSmallestSum(nums1, nums2, k)); // Output: 7

Line Notes

let j = nums2.length - 1Pointer j starts at end of nums2

while (j >= 0 && nums1[i] + nums2[j] > mid)Move j left to find valid pairs

count += (j + 1)Add count of valid pairs for current i

let low = nums1[0] + nums2[0]Initialize low bound

let high = nums1[nums1.length - 1] + nums2[nums2.length - 1]Initialize high bound

while (low < high)Binary search loop

if (countPairs(...) < k)Adjust low if fewer pairs ≤ mid

else { high = mid; }Adjust high otherwise

return lowReturn k-th smallest sum

⏱

Complexity

TimeO((n + m) log(maxSum - minSum))

SpaceO(1)

Each binary search iteration counts pairs in O(n + m) time. The number of iterations depends on the sum range.

💡 If sum range is large, this can be slower than heap for small k, but uses less memory.

Interview Verdict: Accepted

This approach is efficient and uses constant space, suitable when memory is constrained or arrays are very large.

📊

All Approaches - One-Glance Tradeoffs

💡 The heap approach (Approach 2) is the best to code in interviews for its balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n*m log(n*m))	O(n*m)	No	N/A	Mention only - never code
2. Min-Heap with Visited Set	O(k log k)	O(k)	No	Yes	Code this approach
3. Binary Search on Sum Range	O((n + m) log(maxSum - minSum))	O(1)	No	No	Mention as alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, followed by the heap approach as the optimal solution. Finally, mention binary search as an alternative.

How to Present

Step 1: Clarify input sizes, sorting, and constraints.Step 2: Describe brute force approach and its inefficiency.Step 3: Introduce min-heap with visited set to efficiently find k-th smallest sum.Step 4: Optionally discuss binary search on sum range for alternative solution.Step 5: Code the heap approach carefully, explaining visited set usage.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 12min → Test: 5min. Total ~25min

What the Interviewer Tests

Understanding of heap usage for k-way merge, ability to prune search space with visited sets, and knowledge of binary search on answer space.

Common Follow-ups

• What if arrays are not sorted? → Sort first or use a different approach.
• How to handle duplicates in arrays? → Visited set prevents duplicate pairs.

💡 These follow-ups test your ability to adapt the solution to real-world variations and edge cases.

🔍

Pattern Recognition

When to Use

1) Two sorted arrays given, 2) Need k-th smallest sum of pairs, 3) Naive enumeration too large, 4) Min-heap or binary search can prune search space.

Signature Phrases

k-th smallest sumtwo sorted arraysmin heapvisited set

NOT This Pattern When

Problems that ask for k-th smallest element in a single sorted array or unsorted arrays without pair sums.

Similar Problems

Find K Pairs with Smallest Sums - similar heap-based pair expansionMerge K Sorted Lists - similar k-way merge with heapKth Smallest Element in a Sorted Matrix - similar binary search on sum range

Practice

1. Consider the following Python code implementing the optimal binary search approach to find the median of K sorted arrays. Given arrays = [[1,3,5], [2,4,6], [0,7,8]], what is the value of median1 after the binary search loop completes?

easy

A. 6

B. 3

C. 5

D. 4

Solution

1. Step 1: Calculate total length and median indices

   Total length = 3 + 3 + 3 = 9, so mid1 = (9-1)//2 = 4.

2. Step 2: Perform binary search on value range [0,8]

   Counting elements ≤ mid at each step narrows down to the smallest number with count > 4, which is 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Median of combined sorted array [0,1,2,3,4,5,6,7,8] is 4 [OK]

Hint: Median index 4 corresponds to value 4 in combined arrays [OK]

Common Mistakes:

• Off-by-one in median index
• Miscounting elements ≤ mid
• Confusing median1 and median2

2. The following code attempts to find the smallest range covering k sorted lists using a min-heap. Identify the line containing the subtle bug that can cause incorrect results or runtime errors.

medium

A. Line popping the smallest element from the heap

B. Line checking if ele_idx + 1 == len(nums[list_idx]) to break the loop

C. Line updating current_max after pushing next_val into the heap

D. Line initializing min_range to float('inf')

Solution

1. Step 1: Identify the role of current_max

   current_max tracks the maximum element in the current window; it must be updated when pushing a new element.

2. Step 2: Locate missing update

   The code comment indicates current_max is not updated after pushing next_val, causing incorrect range calculation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Without updating current_max, range may be underestimated or incorrect [OK]

Hint: Always update current_max after pushing new heap element [OK]

Common Mistakes:

• Forgetting to update current_max after pushing new element
• Breaking loop too early or too late
• Misusing heap pop or initialization

3. Consider this modified code snippet for nth super ugly number. Which line contains a subtle bug that can cause incorrect results?

medium

A. Line where val is appended to ugly without checking duplicates

B. Line where initial primes are pushed into the heap

C. Line where heap is initialized as an empty list

D. Line where new heap element is pushed with updated index

Solution

1. Step 1: Identify difference from correct code

   The original code checks if val != ugly[-1] before appending to avoid duplicates.

2. Step 2: Understand impact of missing duplicate check

   Appending duplicates causes the sequence to have repeated numbers, leading to incorrect nth number.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicate values break the strictly increasing sequence [OK]

Hint: Check for duplicate filtering when appending new ugly numbers [OK]

Common Mistakes:

• Forgetting to skip duplicates when popping from heap
• Incorrect heap push indices
• Misinitializing heap elements

4. Suppose you want to find the median of K sorted arrays where elements can be reused infinitely (i.e., arrays represent multisets with unlimited copies). Which modification to the optimal binary search approach is correct?

hard

A. Use the same binary search counting method since counts remain valid with infinite reuse.

B. Modify counting to multiply bisect counts by infinity, which is not feasible; thus binary search fails here.

C. Use binary search on value range but replace counting with a formula based on frequency and reuse constraints.

D. Switch to a heap-based approach that tracks counts and duplicates explicitly to handle infinite reuse.

Solution

1. Step 1: Understand infinite reuse impact

   Infinite reuse means counts are unbounded; naive counting fails.

2. Step 2: Adapt counting method

   Counting must use frequency and reuse constraints to compute how many elements ≤ mid considering infinite copies.

3. Step 3: Modify binary search accordingly

   Binary search on value range remains valid but counting function must be formula-based, not bisect-based.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Counting must reflect reuse; naive bisect counting breaks [OK]

Hint: Infinite reuse breaks bisect counting; formula needed [OK]

Common Mistakes:

• Assuming bisect counting works with infinite reuse
• Switching to heap unnecessarily
• Ignoring reuse constraints in counting

5. Suppose you want to merge k sorted lists but now each list can contain duplicate values that must be preserved, and you want to return the top M smallest elements overall efficiently. Which modification to the standard divide and conquer approach is best?

hard

A. Continue using divide and conquer merging all lists fully, then slice the first M elements from the merged list.

B. Use dynamic programming to memoize merged prefixes and retrieve top M elements.

C. Concatenate all lists, sort them fully, then return first M elements.

D. Use a min heap to always extract the smallest current node among all lists until M elements are collected.

Solution

1. Step 1: Understand the requirement for top M elements

   We only need the first M smallest elements, not the full merged list.

2. Step 2: Analyze approaches for efficiency

   Divide and conquer merges all lists fully (O(N log k)), which is wasteful if M << N. Concatenation and sort is O(N log N). Min heap approach extracts smallest nodes one by one, stopping after M elements, achieving O(M log k).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min heap approach efficiently returns top M elements without full merge [OK]

Hint: Min heap extracts smallest nodes incrementally, ideal for top M [OK]

Common Mistakes:

• Merging all lists fully then slicing wastes time
• Sorting all nodes is inefficient for partial results
• Dynamic programming is not applicable here