[Leetcode] 373. Find K Pairs with Smallest Sums

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/?envType=study-plan-v2&envId=top-interview-150https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/?envType=study-plan-v2&envId=top-interview-150

initial

i thoguth of getting the first k elements from each arrays, sort based on the sums and return k combinations. That works but there is a better way

intial thought

def kSmallestPairs_optimized_bruteforce(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    """
    Optimized brute force: Only generate first k elements from each array
    Time: O(k²*log(k²)), Space: O(k²)
    """
    pairs = []
    
    # Only consider first k elements from each array (since arrays are sorted)
    limit1 = min(len(nums1), k)
    limit2 = min(len(nums2), k)
    
    for i in range(limit1):
        for j in range(limit2):
            pairs.append([nums1[i], nums2[j], nums1[i] + nums2[j]])
    
    pairs.sort(key=lambda x: x[2])
    return [[pair[0], pair[1]] for pair in pairs[:k]]

sol

actually we can think of a matrix. for (0,0) starting position, we traverse towards (0,1) and (1,0) cuz tat will give us the lowest value. Not (3,4) like in the middle of matrix but along the edges of starting point 0,0.

like

    Think of it like exploring a 2D grid where:
    - Row i = nums1[i], Column j = nums2[j] 
    - Each cell (i,j) has value nums1[i] + nums2[j]
    - We want the k smallest values
    
    Example: nums1=[1,7,11], nums2=[2,4,6]
    Grid looks like:
           j=0  j=1  j=2
           (2)  (4)  (6)
    i=0(1)  3    5    7
    i=1(7)  9   11   13  
    i=2(11) 13  15   17
    
    We start at top-left (smallest) and expand smartly!

btw there shuld be a comma in between the visiting position like 0,0 and not 00 cuz later we cannot differentiate 1010 like it can be 10,10 or 101,0.

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a-> a[0]));
        pq.offer(new int[]{nums1[0]+nums2[0],0,0});
        List<List<Integer>> ans = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        visited.add("0"+","+"0");
        while(pq.size()!=0 && ans.size()<k){
            int[] now = pq.poll();
            int sum=now[0],i=now[1],j=now[2];
            ans.add(Arrays.asList(nums1[i],nums2[j]));
            if(i+1<(nums1.length)){
                String key = (i+1)+","+j; 
                if(!visited.contains(key)){
                    pq.offer(new int[]{nums1[i+1]+nums2[j],i+1,j});
                    visited.add(key);
                }
            }
            if(j+1<(nums2.length)){
                String key = i+","+(j+1); 
                if(!visited.contains(key)){
                    pq.offer(new int[]{nums1[i]+nums2[j+1],i,j+1});
                    visited.add(key);
                }
            }
        }
        return ans;
    }
}

complexity

the while iterations run exactly for k number of operations while heap operations are log k time
so its k log k time
heap stores max k number of elements so k space