Day 26 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/find-k-smallest-sum-pairs/1

Find K Smallest Sum Pairs

Difficulty: Medium Accuracy: 62.51%

Given two integer arrays arr1[] and arr2[] sorted in ascending order and an integer k, your task is to find k pairs with the smallest sums, such that one element of each pair belongs to arr1[] and the other belongs to arr2[].
Return the list of these k pairs, where each pair is represented as [arr1[i], arr2[j]].
Note: You can return any possible k pairs with the smallest sums, the driver code will print true if it is correct else it will print false.

Examples:
Input: arr1[] = [1, 7, 11], arr2[] = [2, 4, 6], k = 3
Output: true
Explanation: All possible combinations of elements from the two arrays are:
[1, 2], [1, 4], [1, 6], [7, 2], [7, 4], [7, 6], [11, 2], [11, 4], [11, 6].
Among these, the three pairs with the minimum sums are [1, 2], [1, 4], [1, 6].
Input: arr1[] = [1, 3], arr2[] = [2, 4] k = 2
Output: true
Explanation: All possible combinations are [1, 2], [1, 4], [3, 2], [3, 4].
Among these, the two pairs with the minimum sums are [1, 2], [3, 2].
Constraints:
1 ≤ arr1.size(), arr2.size() ≤ 5*104
1 ≤ arr1[i], arr2[j] ≤ 109
1 ≤ k ≤ 103

Solution:

import heapq

class Solution:
def kSmallestPair(self, arr1, arr2, k):
heap, res = [], []
for i in range(min(k, len(arr1))):
heapq.heappush(heap, (arr1[i] + arr2[0], i, 0))
while heap and len(res) < k:
s, i, j = heapq.heappop(heap)
res.append([arr1[i], arr2[j]])
if j + 1 < len(arr2):
heapq.heappush(heap, (arr1[i] + arr2[j + 1], i, j + 1))
return res