package com.fishercoder.solutions;

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

/**
 *  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 {

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

    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> result = new ArrayList<int[]>();
        if (nums1 == null || nums2 == null || k == 0 || nums1.length == 0 || nums2.length == 0) {
            return result;
        }
        Queue<Node> meanHeap = new PriorityQueue<Node>();
        meanHeap.offer(new Node(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()) {
            Node node = meanHeap.poll();
            result.add(new int[]{nums1[node.row], nums2[node.col]});
            k--;
            for (int[] neighbor : neighbors) {
                int nextRow = node.row + neighbor[0];
                int nextCol = node.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 Node(nextRow, nextCol, nums1[nextRow] + nums2[nextCol]));
            }
        }


        return result;
    }

    private class Node implements Comparable<Node> {
        int row;
        int col;
        int sum;

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

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

}

@@ -144,16 +144,58 @@
 %0A/**%0A * 
+373. Find K Pairs with Smallest Sums%0A *%0A *
  You are
@@ -280,17 +280,18 @@
 eger k.%0A
-%0A
+ *
  Define 
@@ -393,17 +393,18 @@
  array.%0A
-%0A
+ *
  Find th
@@ -477,17 +477,16 @@
 mple 1:%0A
-%0A
  Given n
@@ -518,33 +518,32 @@
 %5B2,4,6%5D,  k = 3%0A
-%0A
  Return: %5B1,2%5D,%5B
@@ -553,17 +553,16 @@
 %5D,%5B1,6%5D%0A
-%0A
  The fir
@@ -675,17 +675,16 @@
 mple 2:%0A
-%0A
  Given n
@@ -723,17 +723,16 @@
   k = 2%0A
-%0A
  Return:
@@ -744,17 +744,16 @@
 %5D,%5B1,1%5D%0A
-%0A
  The fir
@@ -863,17 +863,16 @@
 mple 3:%0A
-%0A
  Given n
@@ -905,17 +905,16 @@
   k = 3%0A
-%0A
  Return:
@@ -926,17 +926,16 @@
 %5D,%5B2,3%5D%0A
-%0A
  All pos
@@ -1193,21 +1193,16 @@
 rayList%3C
-int%5B%5D
 %3E();%0A   
@@ -1347,20 +1347,20 @@
   Queue%3C
-Node
+Pair
 %3E meanHe
@@ -1382,20 +1382,16 @@
 tyQueue%3C
-Node
 %3E();%0A   
@@ -1414,20 +1414,20 @@
 fer(new 
-Node
+Pair
 (0, 0, n
@@ -1656,17 +1656,17 @@
     
-Node node
+Pair pair
  = m
@@ -1720,20 +1720,20 @@
 %5D%7Bnums1%5B
-node
+pair
 .row%5D, n
@@ -1737,20 +1737,20 @@
 , nums2%5B
-node
+pair
 .col%5D%7D);
@@ -1844,20 +1844,20 @@
 xtRow = 
-node
+pair
 .row + n
@@ -1902,12 +1902,12 @@
 l = 
-node
+pair
 .col
@@ -2188,20 +2188,20 @@
 fer(new 
-Node
+Pair
 (nextRow
@@ -2310,26 +2310,18 @@
     
-private 
 class 
-Node
+Pair
  imp
@@ -2339,20 +2339,20 @@
 parable%3C
-Node
+Pair
 %3E %7B%0A    
@@ -2414,20 +2414,20 @@
  public 
-Node
+Pair
 (int row
@@ -2594,12 +2594,12 @@
 eTo(
-Node
+Pair
  tha

refactor 373