educative.io

Educative

It seems like a simple linear solution would be a bit better in this case

Something like this:

public static List<int[]> findKLargestPairs(int[] nums1, int[] nums2, int k) {
    List<int[]> result = new ArrayList<>();
    
    if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0 || k <= 0) {
      return result;
    }

    int idx1 = 0;
    int idx2 = 0;
    while(result.size() < k) {
      result.add(new int[]{nums1[idx1], nums2[idx2]});

      if(idx1 + 1 == nums1.length && idx2 + 1 == nums2.length) {
        break;
      }

      if(idx1 + 1 < nums1.length && result.size() < k) {
        result.add(new int[]{nums1[idx1 + 1], nums2[idx2]});
      }
      if(idx2 + 1 < nums2.length && result.size() < k) {
        result.add(new int[]{nums1[idx1], nums2[idx2 + 1]});
      }

      if(idx1 + 1 < nums1.length) {
        idx1++;
      }
      if(idx2 + 1 < nums2.length) {
        idx2++;
      }
    }

    return result;
  }

Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Problem Challenge 1 - Grokking the Coding Interview: Patterns for Coding Questions


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Problem Challenge 1 - Grokking the Coding Interview: Patterns for Coding Questions

Hi @Peter_Litvak, Yes this is also an alternative solution for this question. However, the solution we are going for within our course is using data structures like minheap since this course is focusing on how to excel in a coding interview, and is discussing the pattern of questions and their most desirable solutions. Hence, we have given the solution which is going to help the candidate score the most points in an interview.

Thanks!