Added 2 solutions & modified 1 solution

varunu28 · varunu28 · commit e96eb1960bf2 · 2020-08-06T10:20:45.000-05:00
diff --git a/Hard/Shortest Distance from All Buildings.java b/Hard/Shortest Distance from All Buildings.java
@@ -0,0 +1,56 @@
+class Solution {
+  int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
+  public int shortestDistance(int[][] grid) {
+    int numOfHouses = 0;
+    for (int i = 0; i < grid.length; i++) {
+      for (int j = 0; j < grid[0].length; j++) {
+        numOfHouses += grid[i][j] == 1 ? 1 : 0;
+      }
+    }
+    int[] distance = {Integer.MAX_VALUE};
+    for (int i = 0; i < grid.length; i++) {
+      for (int j = 0; j < grid[0].length; j++) {
+        if (grid[i][j] == 0) {
+          bfs(grid, i, j, numOfHouses, distance);
+        }
+      }
+    }
+    return distance[0] == Integer.MAX_VALUE ? -1 : distance[0];
+  }
+  
+  private void bfs(int[][] grid, int i, int j, int numOfHouses, int[] distance) {
+    int currDistance = 0;
+    int numRows = grid.length;
+    int numCols = grid[0].length;
+    int houses = 0;
+    boolean[][] visited = new boolean[numRows][numCols];
+    Queue<int[]> queue = new LinkedList<>();
+    queue.add(new int[]{i, j, 0});
+    visited[i][j] = true;
+    while (!queue.isEmpty() && houses != numOfHouses) {
+      int size = queue.size();
+      while (size-- > 0) {
+        int[] removed = queue.remove();
+        int x = removed[0];
+        int y = removed[1];
+        if (grid[x][y] == 1) {
+          houses++;
+          currDistance += removed[2];
+        }
+        else if (grid[x][y] == 0) {
+          for (int[] dir : dirs) {
+            int newX = x + dir[0];
+            int newY = y + dir[1];
+            if (newX >= 0 && newX < numRows && newY >= 0 && newY < numCols && !visited[newX][newY]) {
+              queue.add(new int[]{newX, newY, removed[2] + 1});
+              visited[newX][newY] = true;
+            }
+          }
+        }
+      }
+    }
+    if (houses == numOfHouses) {
+      distance[0] = Math.min(distance[0], currDistance);
+    }
+  }
+}
diff --git a/Medium/Convert Binary Search Tree to Sorted Doubly Linked List.java b/Medium/Convert Binary Search Tree to Sorted Doubly Linked List.java
@@ -7,43 +7,40 @@ class Node {
 
     public Node() {}
 
+    public Node(int _val) {
+        val = _val;
+    }
+
     public Node(int _val,Node _left,Node _right) {
         val = _val;
         left = _left;
         right = _right;
     }
 };
 */
+
 class Solution {
-    Node prev;
-    public Node treeToDoublyList(Node r) {
-        if (r == null) {
-            return r;
-        }
-        
-        prev = null;
-        Node dummy = new Node(0);
-        prev = dummy;
-        
-        inorderHelper(r);
-        
-        prev.right = dummy.right;
-        dummy.right.left = prev;
-        
-        return dummy.right;
+  Node prev;
+  public Node treeToDoublyList(Node root) {
+    if (root == null) {
+      return root;
     }
-    
-    private void inorderHelper(Node root) {
-        if (root == null) {
-            return;
-        }
-        
-        inorderHelper(root.left);
-        
-        prev.right = root;
-        root.left = prev;
-        prev = root;
-        
-        inorderHelper(root.right);
+    Node dummy = new Node(0);
+    prev = dummy;
+    helper(root);
+    prev.right = dummy.right;
+    dummy.right.left = prev;
+    return dummy.right;
+  }
+  
+  private void helper(Node root) {
+    if (root == null) {
+      return;
     }
+    helper(root.left);
+    prev.right = root;
+    root.left = prev;
+    prev = root;
+    helper(root.right); 
+  }
 }
diff --git a/Medium/Sparse Matrix Multiplication.java b/Medium/Sparse Matrix Multiplication.java
@@ -0,0 +1,20 @@
+class Solution {
+  public int[][] multiply(int[][] A, int[][] B) {
+    int m = A.length;
+    int n = A[0].length;
+    int nB = B[0].length;
+    int[][] C = new int[m][nB];
+    for(int i = 0; i < m; i++) {
+      for(int k = 0; k < n; k++) {
+        if (A[i][k] != 0) {
+          for (int j = 0; j < nB; j++) {
+            if (B[k][j] != 0) {
+              C[i][j] += A[i][k] * B[k][j];
+            }
+          }
+        }
+      }
+    }
+    return C;   
+  }
+}
