What is the time complexity of Find K Pairs with Smallest Sums?

The optimal solution has a time complexity of O(k log k).

What data structures are used to solve Find K Pairs with Smallest Sums?

This problem uses Array, Heap (Priority Queue). Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Find K Pairs with Smallest Sums?

Insight 1: Using a min-heap (priority queue) is crucial for efficiently tracking the smallest sums. It allows us to retrieve the smallest sum at any given moment. Insight 2: The sorted nature of the input arrays allows for an optimization. We don't need to compute all possible pairs upfront. We can initially consider pairs formed by the first element of `nums2` with the first few elements of `nums1` (up to 'k' elements).

Which companies ask LeetCode 373. Find K Pairs with Smallest Sums in interviews?

This problem is frequently asked at LinkedIn.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Find K Pairs with Smallest Sums - LeetCode 373 Solution

Find K Pairs with Smallest Sums - Complete Solution Guide

Find K Pairs with Smallest Sums is LeetCode problem 373, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k . Define a pair (u, v) which consists of one element from the first array and one element from the second array. Return the k pairs (u 1 , v 1 ), (u 2 , v 2 ), ..., (u k , v k ) with the smallest sums . Example 1: Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 Output: [[1,2],[1,4],[1,6]] Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],

Detailed Explanation

The problem asks us to find the 'k' pairs with the smallest sums from two sorted integer arrays, `nums1` and `nums2`. A pair consists of one element from `nums1` and one element from `nums2`. The output should be a list of these 'k' pairs, ordered by their sums in ascending order. The constraints specify that both arrays are sorted in non-decreasing order, and 'k' is within reasonable bounds. We are guaranteed that k is less than or equal to the product of the lengths of the input arrays.

Solution Approach

The provided solution uses a min-heap to efficiently find the k smallest pairs. It leverages the sorted nature of the input arrays. It maintains a min-heap of (sum, index_in_nums1, index_in_nums2) tuples. Initially, it adds pairs formed by elements from nums1 (up to k elements) and the first element of nums2 into the heap. Then, it iteratively extracts the pair with the smallest sum from the heap, adds it to the result, and adds the next possible pair (same element from nums1, next element from nums2) back into the heap if the next element exists in nums2. The loop continues until k pairs are found or the heap is empty.

Step-by-Step Algorithm

Step 1: Initialize an empty min-heap (priority queue) to store tuples of (sum, index_in_nums1, index_in_nums2).
Step 2: Initialize an empty result list to store the k smallest pairs.
Step 3: Iterate through the first 'k' elements (or all elements if nums1.length < k) of nums1. For each element, create a pair with the first element of nums2 and push (sum, index_in_nums1, 0) onto the min-heap.
Step 4: While k > 0 and the min-heap is not empty, do the following:
Step 5: Pop the element with the smallest sum from the min-heap. This gives you (sum, i, j), where 'i' is the index in nums1 and 'j' is the index in nums2.
Step 6: Create a pair (nums1[i], nums2[j]) and add it to the result list.
Step 7: Decrement k.
Step 8: If j + 1 is within the bounds of nums2, create a new pair using nums1[i] and nums2[j+1], and push (sum = nums1[i] + nums2[j+1], i, j+1) onto the min-heap.
Step 9: Return the result list.

Key Insights

Insight 1: Using a min-heap (priority queue) is crucial for efficiently tracking the smallest sums. It allows us to retrieve the smallest sum at any given moment.
Insight 2: The sorted nature of the input arrays allows for an optimization. We don't need to compute all possible pairs upfront. We can initially consider pairs formed by the first element of `nums2` with the first few elements of `nums1` (up to 'k' elements).
Insight 3: Instead of re-sorting elements after adding a new element, the heap property can be maintained by pushing an element only when a smaller sum has been achieved.

Complexity Analysis

Time Complexity: O(k log k)

Space Complexity: O(k)

Topics

This problem involves: Array, Heap (Priority Queue).

Companies

Asked at: LinkedIn.

Find K Pairs with Smallest Sums | LeetCode 373

Medium

Array Heap (Priority Queue)

Time: O(k log k)Space: O(k)

Solution Code

Available in:

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

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0 || k == 0) {
            return new ArrayList<>();
        }

        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> (a[0] + a[1]) - (b[0] + b[1]));
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            minHeap.offer(new int[]{nums1[i], nums2[0], i, 0});
        }

        while (k > 0 && !minHeap.isEmpty()) {
            int[] current = minHeap.poll();
            int i = current[2];
            int j = current[3];

            List<Integer> pair = new ArrayList<>();
            pair.add(nums1[i]);
            pair.add(nums2[j]);
            result.add(pair);

            k--;

            if (j + 1 < nums2.length) {
                minHeap.offer(new int[]{nums1[i], nums2[j + 1], i, j + 1});
            }
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 373: Find K Pairs with Smallest Sums - Detailed explanation and solution approaches.

Topics

Array Heap (Priority Queue)

Companies

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:373

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize an empty min-heap (priority queue) to store tuples of (sum, index_in_nums1, index_in_nums2).
2
Step 2: Initialize an empty result list to store the k smallest pairs.
3
Step 3: Iterate through the first 'k' elements (or all elements if nums1.length < k) of nums1. For each element, create a pair with the first element of nums2 and push (sum, index_in_nums1, 0) onto the min-heap.
4
Step 4: While k > 0 and the min-heap is not empty, do the following:
5
Step 5: Pop the element with the smallest sum from the min-heap. This gives you (sum, i, j), where 'i' is the index in nums1 and 'j' is the index in nums2.
6
Step 6: Create a pair (nums1[i], nums2[j]) and add it to the result list.
7
Step 7: Decrement k.
8
Step 8: If j + 1 is within the bounds of nums2, create a new pair using nums1[i] and nums2[j+1], and push (sum = nums1[i] + nums2[j+1], i, j+1) onto the min-heap.
9
Step 9: Return the result list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(k log k)

💾

Space Complexity

O(k)

📝

Why?

The time complexity is dominated by the heap operations. The heap initially has min(k, len(nums1)) elements. In the worst case, we extract 'k' elements from the heap, and for each extraction, we might add a new element to the heap. Thus, we have O(k) heap operations, each taking O(log min(k, len(nums1))) time. The space complexity is determined by the size of the heap, which is at most min(k, len(nums1)). The result list contains at most 'k' pairs, but that does not change the space complexity order.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Generate all possible pairs, calculate their sums, and then sort them to find the k smallest. This can be implemented using sorting algorithms.

Time: O(m * n log(m * n)), where m and n are the lengths of nums1 and nums2, respectively. Generating all pairs takes O(m*n) time and sorting takes O(m*n log(m*n)).Space: O(m * n). We store all possible pairs.

Trade-offs: This approach is simpler to understand but much less efficient for large inputs. It is generally not recommended due to its poor time complexity compared to the heap-based solution. It's only beneficial if m*n is extremely small.

✨

Key Insights

1Insight 1: Using a min-heap (priority queue) is crucial for efficiently tracking the smallest sums. It allows us to retrieve the smallest sum at any given moment.
2Insight 2: The sorted nature of the input arrays allows for an optimization. We don't need to compute all possible pairs upfront. We can initially consider pairs formed by the first element of `nums2` with the first few elements of `nums1` (up to 'k' elements).
3Insight 3: Instead of re-sorting elements after adding a new element, the heap property can be maintained by pushing an element only when a smaller sum has been achieved.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Either `nums1` or `nums2` is empty. The solution handles this by returning an empty list in this case. The initial check `if not nums1 or not nums2 or k == 0:` takes care of this.
Edge case 2: k is larger than the total number of possible pairs (nums1.length * nums2.length). The solution handles this gracefully by stopping when the heap is empty, which happens after all possible pairs have been added to the result. The `while k > 0 and min_heap:` loop condition ensures that it does not continue beyond the number of existing pairs.
Edge case 3: k is 0. The function correctly returns an empty list in this situation.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not using a min-heap and attempting to sort all possible pairs. This leads to a much higher time complexity.

✗Common mistake 2: Incorrectly handling the heap indices. Making sure you keep track of the correct indices in nums1 and nums2 is crucial for adding the correct elements to the heap and the result.

✗Common mistake 3: Failing to consider cases where 'k' is larger than the product of the lengths of the two arrays. The loop conditions need to handle this gracefully.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Recommendation systems where you need to find the k best combinations of items based on some scoring function (e.g., movie preferences or product recommendations). The two input arrays could represent user preferences and item ratings.

🏦Real-world scenario 2: Database query optimization where you want to find the k smallest result sets based on certain query conditions. The two input arrays could represent sorted indices from two different tables, and the pair sums represent the cost of joining those indices.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 14, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

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

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether heap (priority queue) techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?