Added 1 solution & modified 2 solutions

varunu28 · varunu28 · commit e529f20d3ef0 · 2020-01-01T14:07:35.000-08:00
diff --git a/Medium/Interval List Intersections.java b/Medium/Interval List Intersections.java
@@ -1,39 +1,22 @@
 class Solution {
-    public int[][] intervalIntersection(int[][] A, int[][] B) {
-        List<int[]> intersections = new ArrayList<>();
-        int idx1 = 0;
-        int idx2 = 0;
-    
-        while (idx1 < A.length && idx2 < B.length) {
-            if (A[idx1][0] > B[idx2][1]) {
-                idx2++;
-                continue;
-            }
-            
-            if (A[idx1][1] < B[idx2][0]) {
-                idx1++;
-                continue;
-            }
-            
-            int maxStart = Math.max(A[idx1][0], B[idx2][0]);
-            int minEnd = Math.min(A[idx1][1], B[idx2][1]);
-            
-            int[] interval = {maxStart, minEnd};
-            intersections.add(interval);
-            
-            if (A[idx1][1] > B[idx2][1]) {
-                idx2++;
-            }
-            else {
-                idx1++;
-            }
-        }
-        
-        int[][] ans = new int[intersections.size()][2];
-        for (int i = 0; i < intersections.size(); i++) {
-            ans[i] = intersections.get(i);
-        }
-        
-        return ans;
+  public int[][] intervalIntersection(int[][] A, int[][] B) {
+    List<int[]> list = new ArrayList<>();
+    int startA = 0;
+    int startB = 0;
+    while (startA < A.length && startB < B.length) {
+      int intervalStart = Math.max(A[startA][0], B[startB][0]);
+      int intervalEnd = Math.min(A[startA][1], B[startB][1]);
+      if (intervalStart <= intervalEnd) {
+        list.add(new int[]{intervalStart, intervalEnd});
+      }
+      if (A[startA][1] < B[startB][1]) {
+        startA++;
+      }
+      else {
+        startB++;
+      }
     }
+    int[][] ans = new int[list.size()][2];
+    return list.toArray(ans);
+  }
 }
diff --git a/Medium/Minimum Remove to Make Valid Parentheses.java b/Medium/Minimum Remove to Make Valid Parentheses.java
@@ -0,0 +1,29 @@
+class Solution {
+  public String minRemoveToMakeValid(String s) {
+    Stack<Integer> stack = new Stack<>();
+    char[] chars = s.toCharArray();
+    for (int i = 0; i < chars.length; i++) {
+      if (chars[i] == '(') {
+        stack.push(i);
+      }
+      else if (chars[i] == ')') {
+        if (stack.isEmpty()) {
+          chars[i] = '-';
+        }
+        else {
+          stack.pop();
+        }
+      }
+    }
+    while (!stack.isEmpty()) {
+      chars[stack.pop()] = '-';
+    }
+    StringBuilder sb = new StringBuilder();
+    for (int i = 0; i < chars.length; i++) {
+      if (chars[i] != '-') {
+        sb.append(chars[i]);
+      }
+    }
+    return sb.toString();
+  }
+}
diff --git a/Medium/Vertical Order Traversal Of Binary Tree.java b/Medium/Vertical Order Traversal Of Binary Tree.java
@@ -8,95 +8,56 @@
  * }
  */
 class Solution {
-    class NewNode {
-        TreeNode t;
-        int x;
-        int y;
-        int level;
-        
-        NewNode(TreeNode t, int x, int y, int level) {
-            this.t = t;
-            this.x = x;
-            this.y = y;
-            this.level = level;
-        }
+  public List<List<Integer>> verticalTraversal(TreeNode root) {
+    if (root == null) {
+      return new ArrayList<>();
     }
-    
-    int maxLeft;
-    int maxRight;
-    Map<Integer, List<NewNode>> map;
-    
-    public List<List<Integer>> verticalTraversal(TreeNode root) {
-        maxLeft = 0;    
-        maxRight = 0;
-        map = new HashMap<>();
-        
-        helper(root, 0);
-        
-        List<List<Integer>> list = new ArrayList<>();
-        
-        while (maxLeft <= maxRight) {
-            if (map.containsKey(maxLeft)) {
-                List<NewNode> temp = map.get(maxLeft);
-                
-                Collections.sort(temp, new Comparator<NewNode>() {
-                    @Override
-                    public int compare(NewNode o1, NewNode o2) {
-                        int c = Integer.valueOf(o1.x).compareTo(Integer.valueOf(o2.x));
-                        if (c == 0) {
-                            c = Integer.valueOf(o2.y).compareTo(Integer.valueOf(o1.y));
-                        }
-                        
-                        if (c == 0) {
-                            c = Integer.valueOf(o1.t.val).compareTo(Integer.valueOf(o2.t.val));
-                        }
-                        
-                        return c;
-                    }
-                });
-                
-                List<Integer> valList = new ArrayList<>();
-                for (NewNode node : temp) {
-                    valList.add(node.t.val);
-                }
-                
-                list.add(valList);
-            }
-            
-            maxLeft++;
+    Map<Integer, List<TreeLevel>> map = new TreeMap<>();
+    Queue<TreeLevel> queue = new LinkedList<>();
+    queue.add(new TreeLevel(root, 0, 0));
+    while (!queue.isEmpty()) {
+      int size = queue.size();
+      while (size-- > 0) {
+        TreeLevel removed = queue.remove();
+        map.computeIfAbsent(removed.xLevel, k -> new ArrayList<>()).add(removed);
+        if (removed.node.left != null) {
+          queue.add(new TreeLevel(removed.node.left, removed.xLevel - 1, removed.yLevel - 1));
         }
-        
-        return list;
-    }
-    
-    private void helper(TreeNode root, int level) {
-        if (root == null) {
-            return;
+        if (removed.node.right != null) {
+          queue.add(new TreeLevel(removed.node.right, removed.xLevel + 1, removed.yLevel - 1));
         }
-        
-        NewNode node = new NewNode(root, 0, 0, level);
-        Queue<NewNode> queue = new LinkedList<>();
-        
-        queue.add(node);
-        
-        while (!queue.isEmpty()) {
-            int size = queue.size();
-            
-            while (size-- > 0) {
-                NewNode temp = queue.remove();
-                map.computeIfAbsent(temp.level, k -> new ArrayList<>()).add(temp);
-                
-                maxLeft = Math.min(maxLeft, temp.level - 1);
-                maxRight = Math.max(maxRight, temp.level + 1);
-                
-                if (temp.t.left != null) {
-                    queue.add(new NewNode(temp.t.left, temp.x - 1, temp.y - 1, temp.level - 1));
-                }
-                
-                if (temp.t.right != null) {
-                    queue.add(new NewNode(temp.t.right, temp.x + 1, temp.y - 1, temp.level + 1));
-                }
-            }
+      }
+    }
+    List<List<Integer>> list = new ArrayList<>();
+    for (Integer key : map.keySet()) {
+      List<TreeLevel> temp = map.get(key);
+      Collections.sort(temp, new Comparator<TreeLevel>(){
+        public int compare(TreeLevel t1, TreeLevel t2) {
+          int c = t2.yLevel - t1.yLevel;
+          if (c == 0) {
+            c = t1.node.val - t2.node.val;
+          }
+          return c;
         }
+      });
+      List<Integer> valTemp = new ArrayList<>();
+      for (TreeLevel t : temp) {
+        valTemp.add(t.node.val);
+      }
+      list.add(valTemp);
     }
+    return list;
+  }
+}
+
+class TreeLevel {
+  TreeNode node;
+  int xLevel;
+  int yLevel;
+  
+  public TreeLevel(TreeNode node, int xLevel, int yLevel) {
+    this.node = node;
+    this.xLevel = xLevel;
+    this.yLevel = yLevel;
+  }
 }
