Added 2 solutions & modified 3 solutions

varunu28 · varunu28 · commit baade582ee78 · 2020-08-01T15:33:29.000-05:00
diff --git a/Hard/Odd Even Jump.java b/Hard/Odd Even Jump.java
@@ -1,33 +1,36 @@
 class Solution {
-    public int oddEvenJumps(int[] A) {
-        if (A.length <= 1) {
-            return A.length;
+  public int oddEvenJumps(int[] A) {
+    int n = A.length;
+    if (n <= 1) {
+      return n;
+    }
+    boolean[] odd = new boolean[n];
+    boolean[] even = new boolean[n];
+    odd[n - 1] = even[n - 1] = true;
+    TreeMap<Integer, Integer> map = new TreeMap<>();
+    map.put(A[n - 1], n - 1);
+    int count = 0;
+    for (int i = n - 2; i >= 0; i--) {
+      int val = A[i];
+      if (map.containsKey(val)) {
+        odd[i] = even[map.get(val)];
+        even[i] = odd[map.get(val)];
+      }
+      else {
+        Integer lower = map.lowerKey(val);
+        Integer higher = map.higherKey(val);
+        if (lower != null) {
+          even[i] = odd[map.get(lower)];
         }
-        boolean[] odd = new boolean[A.length];
-        boolean[] even = new boolean[A.length];
-        odd[A.length - 1] = even[A.length - 1] = true;
-        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
-        treeMap.put(A[A.length - 1], A.length - 1);
-        int count = 0;
-        for (int i = A.length - 2; i >= 0; i--) {
-            int val = A[i];
-            if (treeMap.containsKey(val)) {
-                odd[i] = even[treeMap.get(val)];
-                even[i] = odd[treeMap.get(val)];
-            }
-            else {
-                Integer lower = treeMap.lowerKey(val);
-                Integer higher = treeMap.higherKey(val);
-                if (lower != null) {
-                    even[i] = odd[treeMap.get(lower)];
-                }
-                if (higher != null) {
-                    odd[i] = even[treeMap.get(higher)];
-                }
-            }
-            treeMap.put(val, i);
-            count += odd[i] ? 1 : 0;
+        if (higher != null) {
+          odd[i] = even[map.get(higher)];
         }
-        return count + 1;
+      }
+      map.put(val, i);
+    }
+    for (boolean b : odd) {
+      count += b ? 1 : 0;
     }
+    return count;
+  }
 }
diff --git a/Medium/Increasing Triplet Subsequence.java b/Medium/Increasing Triplet Subsequence.java
@@ -0,0 +1,18 @@
+class Solution {
+  public boolean increasingTriplet(int[] nums) {
+    int firstNum = Integer.MAX_VALUE;
+    int secondNum = Integer.MAX_VALUE;
+    for (int num : nums) {
+      if (num <= firstNum) {
+        firstNum = num;
+      }
+      else if (num <= secondNum) {
+        secondNum = num;
+      }
+      else {
+        return true;
+      }
+    }
+    return false;
+  }
+}
diff --git a/Medium/Maximum Level Sum of a Binary Tree.java b/Medium/Maximum Level Sum of a Binary Tree.java
@@ -4,41 +4,44 @@
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
- *     TreeNode(int x) { val = x; }
+ *     TreeNode() {}
+ *     TreeNode(int val) { this.val = val; }
+ *     TreeNode(int val, TreeNode left, TreeNode right) {
+ *         this.val = val;
+ *         this.left = left;
+ *         this.right = right;
+ *     }
  * }
  */
 class Solution {
-    public int maxLevelSum(TreeNode root) {
-        if (root == null) {
-            return 0;
+  public int maxLevelSum(TreeNode root) {
+    if (root == null) {
+      return 0;
+    }
+    int currLevel = 1;
+    int maxSum = Integer.MIN_VALUE;
+    int maxSumLevel = 0;
+    Queue<TreeNode> queue = new LinkedList<>();
+    queue.add(root);
+    while (!queue.isEmpty()) {
+      int size = queue.size();
+      int currSum = 0;
+      while (size-- > 0) {
+        TreeNode removed = queue.remove();
+        currSum += removed.val;
+        if (removed.left != null) {
+          queue.add(removed.left);
         }
-        
-        Queue<TreeNode> queue = new LinkedList<>();
-        queue.add(root);
-        int maxSum = 0;
-        int maxLevel = 1;
-        int currLevel = 1;
-        
-        while (!queue.isEmpty()) {
-            int size = queue.size();
-            int tempSum = 0;
-            while (size-- > 0) {
-                TreeNode removed = queue.remove();
-                tempSum += removed.val;
-                if (removed.left != null) {
-                    queue.add(removed.left);
-                }
-                if (removed.right != null) {
-                    queue.add(removed.right);
-                }
-            }
-            if (maxSum < tempSum) {
-                maxSum = tempSum;
-                maxLevel = currLevel;
-            }
-            currLevel++;
+        if (removed.right != null) {
+          queue.add(removed.right);
         }
-        
-        return maxLevel;
+      }
+      if (maxSum < currSum) {
+        maxSum = currSum;
+        maxSumLevel = currLevel;
+      }
+      currLevel++;
     }
+    return maxSumLevel;
+  }
 }
diff --git a/Medium/Minimum Area Rectangle.java b/Medium/Minimum Area Rectangle.java
@@ -0,0 +1,29 @@
+class Solution {
+  public int minAreaRect(int[][] points) {
+    Map<Integer, List<Integer>> rows = new TreeMap();
+    // Map of key as x coordinate and value as list of y coordinates
+    for (int[] point: points) {
+      int x = point[0];
+      int y = point[1];
+      rows.computeIfAbsent(x, k -> new ArrayList()).add(y);
+    }
+    int ans = Integer.MAX_VALUE;
+    Map<String, Integer> lastX = new HashMap();
+    for (int x: rows.keySet()) {
+      List<Integer> row = rows.get(x);
+      Collections.sort(row);
+      for (int i = 0; i < row.size(); ++i) {
+        for (int j = i + 1; j < row.size(); ++j) {
+          int y1 = row.get(i);
+          int y2 = row.get(j);
+          String code = y1 + ":" + y2;
+          if (lastX.containsKey(code)) {
+            ans = Math.min(ans, (x - lastX.get(code)) * (y2 - y1));
+          }
+          lastX.put(code, x);
+        }
+      }
+    }
+    return ans < Integer.MAX_VALUE ? ans : 0;
+  }
+}
diff --git a/Medium/My Calendar II.java b/Medium/My Calendar II.java
@@ -1,25 +1,23 @@
 class MyCalendarTwo {
-    private List<int[]> books = new ArrayList<>();  
-    
-    public boolean book(int s, int e) {
-        
-        MyCalendar overlaps = new MyCalendar();
-        for (int[] b : books)
-            if (Math.max(b[0], s) < Math.min(b[1], e))
-                if (!overlaps.book(Math.max(b[0], s), Math.min(b[1], e))) return false;
-        books.add(new int[]{ s, e });
-        return true;
-    }
+  TreeMap<Integer, Integer> map;
+  public MyCalendarTwo() {
+    map = new TreeMap<>();
+  }
 
-    private static class MyCalendar {
-        List<int[]> books = new ArrayList<>();
-        public boolean book(int start, int end) {
-            for (int[] b : books)
-                if (Math.max(b[0], start) < Math.min(b[1], end)) return false;
-            books.add(new int[]{ start, end });
-            return true;
-        }
+  public boolean book(int start, int end) {
+    map.put(start, map.getOrDefault(start, 0) + 1);
+    map.put(end, map.getOrDefault(end, 0) - 1);
+    int eventCount = 0;
+    for (int val : map.values()) {
+      eventCount += val;
+      if (eventCount >= 3) {
+        map.put(start, map.get(start) - 1);
+        map.put(end, map.get(end) + 1);
+        return false;
+      }
     }
+    return true;
+  }
 }
 
 /**
