Aug 31, 2020 · Aug 31, 2020
diff --git a/src/main/java/com/fishercoder/solutions/_373.java b/src/main/java/com/fishercoder/solutions/_373.java
 import java.util.Queue;

 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;
  public class Solution {

    int[][] dirs = {{0,1},{1,0},{1,1}};
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

        List<List<Integer>> result = new ArrayList<>();

        // EDGE CASE
        if(nums1==null || nums2==null || nums1.length==0 || nums2.length==0) return result;

        // visited array
        boolean[][] visited = new boolean[nums1.length][nums2.length];

        // Min Heap
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
            return  ( a[0]+a[1] ) - ( b[0]+b[1] ) ;
        });

        int[] temp = new int[]{nums1[0],nums2[0],0,0};
        pq.add(temp);
        visited[0][0]= true;

        while(!pq.isEmpty()){
            int[] arr = pq.poll();
            List<Integer> ls = new ArrayList<>();
            ls.add(arr[0]);ls.add(arr[1]);
            result.add(ls);

            if(result.size()==k) break;
            int i=arr[2],j=arr[3];

            for(int[] dir : dirs){
                int dx=i+dir[0],dy=j+dir[1];
                if(dx<0 || dx>=nums1.length || dy<0 || dy>=nums2.length || visited[dx][dy]) continue;
                pq.add(new int[]{nums1[dx],nums2[dy],dx,dy});
                visited[dx][dy] = true;
            }
        }
        return result;
    }
  }
 }
Original file line number	Diff line number	Diff line change
Expand Up		@@ -6,60 +6,46 @@
		import java.util.Queue;

		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;
		public class Solution {

		int[][] dirs = {{0,1},{1,0},{1,1}};
		public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {

		List<List<Integer>> result = new ArrayList<>();

		// EDGE CASE
		if(nums1==null \|\| nums2==null \|\| nums1.length==0 \|\| nums2.length==0) return result;

		// visited array
		boolean[][] visited = new boolean[nums1.length][nums2.length];

		// Min Heap
		PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
		return ( a[0]+a[1] ) - ( b[0]+b[1] ) ;
		});

		int[] temp = new int[]{nums1[0],nums2[0],0,0};
		pq.add(temp);
		visited[0][0]= true;

		while(!pq.isEmpty()){
		int[] arr = pq.poll();
		List<Integer> ls = new ArrayList<>();
		ls.add(arr[0]);ls.add(arr[1]);
		result.add(ls);

		if(result.size()==k) break;
		int i=arr[2],j=arr[3];

		for(int[] dir : dirs){
		int dx=i+dir[0],dy=j+dir[1];
		if(dx<0 \|\| dx>=nums1.length \|\| dy<0 \|\| dy>=nums2.length \|\| visited[dx][dy]) continue;
		pq.add(new int[]{nums1[dx],nums2[dy],dx,dy});
		visited[dx][dy] = true;
		}
		}
		return result;
		}
		}
		}