# Solving Leetcode Interviews in Seconds with AI: Find K Pairs with Smallest Sums


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "373" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# 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 (u1, v1), (u2, v2), ..., (uk, vk) 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],[11,6]  Example 2:  Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2 Output: [[1,1],[1,1]] Explanation: The first 2 pairs are returned from the sequence: [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]    Constraints:  1 <= nums1.length, nums2.length <= 105 -109 <= nums1[i], nums2[i] <= 109 nums1 and nums2 both are sorted in non-decreasing order. 1 <= k <= 104 k <= nums1.length * nums2.length  

	# Explanation
	*   **Priority Queue (Heap):** Use a min-heap to store pairs and their sums. The heap will always maintain the pair with the smallest sum at the top.
*   **Initialization:** Start by adding pairs formed by the first element of `nums1` with each element of `nums2` to the heap.
*   **Iteration:** Extract the pair with the smallest sum from the heap. Add this pair to the result. Then, add the next possible pair involving the same element from `nums2` to the heap if available.

*   **Runtime Complexity:** O(k log k), **Storage Complexity:** O(k)

	
	# Code
	```python
	import heapq

def kSmallestPairs(nums1, nums2, k):
    """
    Finds the k pairs with the smallest sums from two sorted integer arrays.

    Args:
        nums1: The first sorted integer array.
        nums2: The second sorted integer array.
        k: The number of pairs to return.

    Returns:
        A list of the k pairs with the smallest sums.
    """

    result = []
    heap = []  # Min-heap to store pairs and their sums
    visited = set()

    # Add initial pairs to the heap (first element of nums1 with each element of nums2)
    for i in range(min(len(nums2), k)):
        heapq.heappush(heap, (nums1[0] + nums2[i], 0, i)) # (sum, index in nums1, index in nums2)
        visited.add((0, i)) # Mark as visited

    while k > 0 and heap:
        sum_val, i, j = heapq.heappop(heap)
        result.append([nums1[i], nums2[j]])
        k -= 1

        # Add the next possible pair to the heap (increment nums1 index)
        if i + 1 < len(nums1) and (i + 1, j) not in visited:
            heapq.heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))
            visited.add((i + 1, j))

    return result
	```