Modified 3 solutions

varunu28 · varunu28 · commit 08d4dc58c642 · 2019-07-18T20:57:10.000-07:00
diff --git a/Hard/Longest Increasing Path in a Matrix.java b/Hard/Longest Increasing Path in a Matrix.java
@@ -1,42 +1,36 @@
 class Solution {
-    int[][] dp;
+    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
     public int longestIncreasingPath(int[][] matrix) {
         if (matrix.length == 0 || matrix[0].length == 0) {
             return 0;
         }
         
+        int[][] dp = new int[matrix.length][matrix[0].length];
         int max = 0;
-        dp = new int[matrix.length][matrix[0].length];
-        
         for (int i = 0; i < matrix.length; i++) {
             for (int j = 0; j < matrix[0].length; j++) {
-                max = Math.max(max, getIncreasingPathLength(matrix, i, j, Integer.MIN_VALUE));
+                max = Math.max(max, dfs(matrix, i, j, dp, Integer.MIN_VALUE));
             }
         }
         
         return max;
     }
     
-    private int getIncreasingPathLength(int[][] matrix, int row, int col, int prev) {
-        if (row < 0 || 
-            col < 0 || 
-            row >= matrix.length || 
-            col >= matrix[0].length || 
-            matrix[row][col] <= prev) {
+    private int dfs(int[][] matrix, int x, int y, int[][] dp, int prevVal) {
+        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= prevVal) {
             return 0;
         }
         
-        if (dp[row][col] != 0) {
-            return dp[row][col];
+        if (dp[x][y] != 0) {
+            return dp[x][y];
         }
         
-        int up = getIncreasingPathLength(matrix, row - 1, col, matrix[row][col]);
-        int down = getIncreasingPathLength(matrix, row + 1, col, matrix[row][col]);
-        int right = getIncreasingPathLength(matrix, row, col + 1, matrix[row][col]);
-        int left = getIncreasingPathLength(matrix, row, col - 1, matrix[row][col]);
-        
-        dp[row][col] = 1 + Math.max(Math.max(up, down), Math.max(right, left));
+        int temp = 0;
+        for (int[] dir : dirs) {
+            temp = Math.max(temp, dfs(matrix, x + dir[0], y + dir[1], dp, matrix[x][y]));
+        }
         
-        return dp[row][col];
+        dp[x][y] = temp + 1;
+        return dp[x][y];
     }
 }
diff --git a/Medium/Flatten Nested List Iterator.java b/Medium/Flatten Nested List Iterator.java
@@ -16,41 +16,35 @@
  * }
  */
 public class NestedIterator implements Iterator<Integer> {
-    List<Integer> list;
-    int index;
-    int size;
-    public NestedIterator(List<NestedInteger> nestedList) {
-        list = new ArrayList<>();
-        index = 0;
-        for (NestedInteger n : nestedList) {
-            dfsHelper(n);
-        }
-        
-        size = list.size();
-    }
     
-    private void dfsHelper(NestedInteger n) {
-        if (n.isInteger()) {
-            list.add(n.getInteger());
-        }
-        else {
-            for (NestedInteger ni : n.getList()) {
-                dfsHelper(ni);
-            }
+    Stack<NestedInteger> stack;
+    public NestedIterator(List<NestedInteger> nestedList) {
+        stack = new Stack<>();
+        for (int i = nestedList.size() - 1; i >= 0; i--) {
+            stack.push(nestedList.get(i));
         }
     }
 
     @Override
     public Integer next() {
-        if (index < size) {
-            return list.get(index++);
-        }
-        return -1;
+        return stack.pop().getInteger();
     }
 
     @Override
     public boolean hasNext() {
-        return !(index == size);        
+        while (!stack.isEmpty()) {
+            NestedInteger curr = stack.peek();
+            if (curr.isInteger()) {
+                return true;
+            }
+            
+            NestedInteger temp = stack.pop();
+            for (int i = temp.getList().size() - 1; i >= 0; i--) {
+                stack.push(temp.getList().get(i));
+            }
+        }
+        
+        return false;
     }
 }
 
diff --git a/Medium/Sort Characters By Frequency.java b/Medium/Sort Characters By Frequency.java
@@ -1,47 +1,35 @@
 class Solution {
-    
     public String frequencySort(String s) {
-        Map<Character, Integer> map = new HashMap<>();
-
-        for (int i=0;i<s.length();i++) {
-            if (map.containsKey(s.charAt(i))) {
-                map.put(s.charAt(i), map.get(s.charAt(i))+1);
-            }
-            else {
-                map.put(s.charAt(i), 1);
-            }
+        List<Character> chars = new ArrayList<>();
+        for (char c : s.toCharArray()) {
+            chars.add(c);
         }
 
-        Map<Character, Integer> sortedMap = sortByValue(map);
-
-
-        StringBuilder sb = new StringBuilder("");
-
-        for (Map.Entry<Character,Integer> entry : sortedMap.entrySet()) {
-            String t = String.join("", Collections.nCopies(entry.getValue(), String.valueOf(entry.getKey())));
-            sb.append(t);
+        Map<Character, Integer> map = new HashMap<>();
+        int val = 0;
+        for (char c : chars) {
+            map.put(c, map.getOrDefault(c, 0) + 1);
+            val = Math.max(val, map.get(c));
         }
 
-        return sb.toString();
-    }
-
-    private Map<Character, Integer> sortByValue(Map<Character, Integer> unsortMap) {
-
-        List<Map.Entry<Character, Integer>> list =
-                new LinkedList<Map.Entry<Character, Integer>>(unsortMap.entrySet());
+        Map<Integer, List<Character>> revMap = new HashMap<>();
+        for (Character key : map.keySet()) {
+            revMap.computeIfAbsent(map.get(key), k -> new ArrayList<>()).add(key);
+        }
 
-        Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
-            public int compare(Map.Entry<Character, Integer> o1,
-                               Map.Entry<Character, Integer> o2) {
-                return (o2.getValue()).compareTo(o1.getValue());
+        StringBuilder sb = new StringBuilder();
+        for (int i = val; i >= 0; i--) {
+            if (revMap.containsKey(i)) {
+                List<Character> characters = revMap.get(i);
+                for (Character character : characters) {
+                    int count = i;
+                    while (count-- > 0) {
+                        sb.append(character);
+                    }
+                }
             }
-        });
-
-        Map<Character, Integer> sortedMap = new LinkedHashMap<Character, Integer>();
-        for (Map.Entry<Character, Integer> entry : list) {
-            sortedMap.put(entry.getKey(), entry.getValue());
         }
 
-        return sortedMap;
+        return sb.toString();
     }
 }
