package com.fishercoder.solutions;

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

/**
 * 373. Find K Pairs with Smallest Sums
 *
 * You are given two integer arrays nums1 and nums2 sorted in ascending 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.
 * Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

 Example 1:
 Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3
 Return: [1,2],[1,4],[1,6]
 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:
 Given nums1 = [1,1,2], nums2 = [1,2,3],  k = 2
 Return: [1,1],[1,1]
 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]

 Example 3:
 Given nums1 = [1,2], nums2 = [3],  k = 3
 Return: [1,3],[2,3]
 All possible pairs are returned from the sequence:
 [1,3],[2,3]

 */
public class _373 {
    public static class Solution1 {

        final int[][] neighbors = new int[][] {{0, 1}, {1, 0}};

        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<int[]> result = new ArrayList<>();
            if (nums1 == null
                || nums2 == null
                || k == 0
                || nums1.length == 0
                || nums2.length == 0) {
                return result;
            }
            Queue<Pair> meanHeap = new PriorityQueue<>();
            meanHeap.offer(new Pair(0, 0, nums1[0] + nums2[0]));
            boolean[][] visited = new boolean[nums1.length][nums2.length];
            visited[0][0] = true;//we start form (0,0), so mark it as visited
            while (k > 0 && !meanHeap.isEmpty()) {
                Pair pair = meanHeap.poll();
                result.add(new int[] {nums1[pair.row], nums2[pair.col]});
                k--;
                for (int[] neighbor : neighbors) {
                    int nextRow = pair.row + neighbor[0];
                    int nextCol = pair.col + neighbor[1];
                    if (nextRow < 0
                        || nextCol < 0
                        || nextRow >= nums1.length
                        || nextCol >= nums2.length
                        || visited[nextRow][nextCol]) {
                        continue;
                    }
                    visited[nextRow][nextCol] = true;
                    meanHeap.offer(new Pair(nextRow, nextCol, nums1[nextRow] + nums2[nextCol]));
                }
            }

            return result;
        }

        class Pair implements Comparable<Pair> {
            int row;
            int col;
            int sum;

            public Pair(int row, int col, int sum) {
                this.row = row;
                this.col = col;
                this.sum = sum;
            }

            @Override
            public int compareTo(Pair that) {
                return this.sum - that.sum;
            }
        }
    }
}

@@ -141,867 +141,8 @@
 e;%0A%0A
-/**%0A * 373. Find K Pairs with Smallest Sums%0A *%0A * You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.%0A * Define a pair (u,v) which consists of one element from the first array and one element from the second array.%0A * Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.%0A%0A Example 1:%0A Given nums1 = %5B1,7,11%5D, nums2 = %5B2,4,6%5D,  k = 3%0A Return: %5B1,2%5D,%5B1,4%5D,%5B1,6%5D%0A The first 3 pairs are returned from the sequence:%0A %5B1,2%5D,%5B1,4%5D,%5B1,6%5D,%5B7,2%5D,%5B7,4%5D,%5B11,2%5D,%5B7,6%5D,%5B11,4%5D,%5B11,6%5D%0A%0A Example 2:%0A Given nums1 = %5B1,1,2%5D, nums2 = %5B1,2,3%5D,  k = 2%0A Return: %5B1,1%5D,%5B1,1%5D%0A The first 2 pairs are returned from the sequence:%0A %5B1,1%5D,%5B1,1%5D,%5B1,2%5D,%5B2,1%5D,%5B1,2%5D,%5B2,2%5D,%5B1,3%5D,%5B1,3%5D,%5B2,3%5D%0A%0A Example 3:%0A Given nums1 = %5B1,2%5D, nums2 = %5B3%5D,  k = 3%0A Return: %5B1,3%5D,%5B2,3%5D%0A All possible pairs are returned from the sequence:%0A %5B1,3%5D,%5B2,3%5D%0A%0A */%0A
 publ
@@ -239,17 +239,16 @@
  int%5B%5D%5B%5D
- 
 %7B%7B0, 1%7D,
@@ -425,32 +425,36 @@
                 
+    
 %7C%7C nums2 == null
@@ -446,32 +446,36 @@
 %7C nums2 == null%0A
+    
                 
@@ -496,24 +496,28 @@
             
+    
 %7C%7C nums1.len
@@ -521,24 +521,28 @@
 length == 0%0A
+    
             
@@ -1022,17 +1022,16 @@
 ew int%5B%5D
- 
 %7Bnums1%5Bp
@@ -1299,32 +1299,36 @@
                 
+    
 %7C%7C nextCol %3C 0%0A 
@@ -1322,24 +1322,28 @@
 nextCol %3C 0%0A
+    
             
@@ -1397,32 +1397,36 @@
                 
+    
 %7C%7C nextCol %3E= nu
@@ -1428,32 +1428,36 @@
 %3E= nums2.length%0A
+    
                 

refactor 373