Added 2 solutions & modified 2 solutions

varunu28 · varunu28 · commit d1f5a7bc2a4b · 2019-07-04T15:38:29.000-07:00
diff --git a/Easy/Best time to buy & sell a stock II.java b/Easy/Best time to buy & sell a stock II.java
@@ -0,0 +1,16 @@
+class Solution {
+    public int maxProfit(int[] prices) {
+        int currMin = Integer.MAX_VALUE;
+        int profit = 0;
+        
+        for (int price : prices) {
+            if (price > currMin) {
+                profit += price - currMin;
+            }        
+            
+            currMin = price;
+        }
+        
+        return profit;
+    }
+}
diff --git a/Easy/best_time_to_buy_and_sell_stockII.java b/Easy/best_time_to_buy_and_sell_stockII.java
diff --git a/Hard/Optimal Account Balancing.java b/Hard/Optimal Account Balancing.java
@@ -0,0 +1,73 @@
+class Solution {
+    int min = Integer.MAX_VALUE;
+    public int minTransfers(int[][] transactions) {
+        Map<Integer, Integer> account = new HashMap<>();
+        for (int[] transaction : transactions) {
+            int amount = transaction[2];
+            account.put(transaction[0], account.getOrDefault(transaction[0], 0) + amount);
+            account.put(transaction[1], account.getOrDefault(transaction[1], 0) - amount);
+        }
+        
+        LinkedList<Integer> posBalance = new LinkedList<>();
+        LinkedList<Integer> negBalance = new LinkedList<>();
+        
+        for (Integer key : account.keySet()) {
+            if (account.get(key) < 0) {
+                negBalance.add(account.get(key));
+            }
+            else if (account.get(key) > 0) {
+                posBalance.add(account.get(key));
+            }
+        }
+        
+        dfs(posBalance, negBalance, 0);
+        return min;
+    }
+    
+    private void dfs(List<Integer> posBalance, List<Integer> negBalance, int count) {
+        if (posBalance.size() == 0 || negBalance.size() == 0) {
+            min = Math.min(count, min);
+            return;
+        }
+        
+        if (count >= min) {
+            return;
+        }
+        
+        int posAmount = posBalance.get(0);
+        
+        for(int j = 0; j < negBalance.size(); j++) {
+            int negAmount = negBalance.get(j);
+            int newPositiveVal = Math.max(posAmount + negAmount, 0);
+            int newNegativeVal = Math.min(0, posAmount + negAmount);
+            if (newPositiveVal == 0){
+                posBalance.remove(0);
+            } 
+            else {
+                posBalance.set(0, newPositiveVal);
+            }
+            if (newNegativeVal == 0){
+                negBalance.remove(j);
+            }
+            else{
+                negBalance.set(j, newNegativeVal);
+            }
+
+            dfs(posBalance, negBalance, count + 1);
+            
+            if(newPositiveVal == 0){
+                posBalance.add(0, posAmount);
+            }
+            else {
+                posBalance.set(0, posAmount);
+            }
+            
+            if(newNegativeVal == 0){
+                negBalance.add(j, negAmount);
+            }
+            else{
+                negBalance.set(j, negAmount);
+            }
+        }
+    }
+}
diff --git a/Hard/Stream of Characters.java b/Hard/Stream of Characters.java
@@ -0,0 +1,65 @@
+class StreamChecker {
+    String[] words;
+    TrieNode root;
+    StringBuilder sb = new StringBuilder();
+    public StreamChecker(String[] words) {
+        this.words = words;
+        root = new TrieNode('#');
+        treeify(words);
+    }
+
+    private void treeify (String[] words) {
+        for (String word : words) {
+            TrieNode curr = root;
+            for (int i = word.length() - 1; i >= 0; i--) {
+                char c = word.charAt(i);
+                if (curr.childrens[c - 'a'] == null) {
+                    curr.childrens[c - 'a'] = new TrieNode(c);
+                }
+
+                curr = curr.childrens[c - 'a'];
+
+                if (i == 0) {
+                    curr.isWord = true;
+                }
+            }
+        }
+    }
+
+    public boolean query(char letter) {
+        sb.append(letter);
+        TrieNode curr = root;
+        for (int i = sb.length() - 1; i >= 0; i--) {
+            if (curr.childrens[sb.charAt(i) - 'a'] != null) {
+                curr = curr.childrens[sb.charAt(i) - 'a'];
+            }
+            else {
+                break;
+            }
+
+            if (curr.isWord) {
+                return true;
+            }
+        }
+
+        return false;
+    }
+
+    class TrieNode {
+        char key;
+        TrieNode[] childrens;
+        boolean isWord;
+
+        public TrieNode (char key) {
+            this.key = key;
+            this.childrens = new TrieNode[26];
+            isWord = false;
+        }
+    }
+}
+
+/**
+ * Your StreamChecker object will be instantiated and called as such:
+ * StreamChecker obj = new StreamChecker(words);
+ * boolean param_1 = obj.query(letter);
+ */
diff --git a/Medium/Minesweeper.java b/Medium/Minesweeper.java
@@ -1,67 +1,43 @@
 class Solution {
-    public char[][] updateBoard(char[][] board, int[] click) {
-        int row = click[0];
-        int col = click[1];
-        
-        updateBoard(board, row, col);
-        
+    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
+    public char[][] updateBoard(char[][] board, int[] click) {    
+        dfs(board, click[0], click[1]);
         return board;
     }
     
-    private void updateBoard(char[][] board, int row, int col) {
-        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) {
+    private void dfs(char[][] board, int x, int y) {
+        if (!isCoordinateValid(x, y, board)) {
             return;
         }
         
-        if (board[row][col] == 'M') {
-            board[row][col] = 'X';
+        if (board[x][y] == 'M') {
+            board[x][y] = 'X';
         }
         
-        if (board[row][col] == 'E') {
-            int mineCount = getMineCount(board, row, col);
+        if (board[x][y] == 'E') {
+            int mineCount = getAdjacentMineCount(board, x, y);
             if (mineCount == 0) {
-                board[row][col] = 'B';
-                updateBoard(board, row + 1, col);
-                updateBoard(board, row, col + 1);
-                updateBoard(board, row, col - 1);
-                updateBoard(board, row - 1, col);
-                updateBoard(board, row - 1, col - 1);
-                updateBoard(board, row + 1, col + 1);
-                updateBoard(board, row - 1, col + 1);
-                updateBoard(board, row + 1, col - 1);
+                board[x][y] = 'B';
+                for (int[] dir : dirs) {
+                    dfs(board, x + dir[0], y + dir[1]);
+                }
             }
             else {
-                board[row][col] = (char) (mineCount + '0');
+                board[x][y] = (char) (mineCount + '0');
             }
-        }
+        }    
     }
     
-    private int getMineCount(char[][] board, int row, int col) {
+    private boolean isCoordinateValid(int x, int y, char[][] board) {
+        return !(x < 0 || x >= board.length || y < 0 || y >= board[0].length);
+    }
+    
+    private int getAdjacentMineCount(char[][] board, int x, int y) {
         int count = 0;
-        
-        if (row + 1 < board.length && board[row + 1][col] == 'M') {
-            count++;
-        } 
-        if (row - 1 >= 0 && board[row - 1][col] == 'M') {
-            count++;
-        }
-        if (col + 1 < board[0].length && board[row][col + 1] == 'M') {
-            count++;
-        }
-        if (col - 1 >= 0 && board[row][col - 1] == 'M') {
-            count++;
-        }
-        if (row + 1 < board.length && col + 1 < board[0].length && board[row + 1][col + 1] == 'M') {
-            count++;
-        }
-        if (row + 1 < board.length && col - 1 >= 0 && board[row + 1][col - 1] == 'M') {
-            count++;
-        }
-        if (row - 1 >= 0 && col + 1 < board[0].length && board[row - 1][col + 1] == 'M') {
-            count++;
-        }
-        if (row - 1 >= 0 && col - 1 >= 0 && board[row - 1][col - 1] == 'M') {
-            count++;
+        for (int[] dir : dirs) {
+            if (isCoordinateValid(x + dir[0], y + dir[1], board) && board[x + dir[0]][y + dir[1]] == 'M') {
+                count++;
+            }
         }
         
         return count;
