Modified 6 solutions

varunu28 · varunu28 · commit 0bf67a9841d9 · 2020-08-05T15:09:43.000-05:00
diff --git a/Medium/Basic Calculator II.java b/Medium/Basic Calculator II.java
@@ -1,39 +1,34 @@
 class Solution {
-    public int calculate(String s) {
-        Stack<Integer> stack = new Stack<>();
-        int num = 0;
-        char sign = '+';
-
-        for (int i=0; i<s.length(); i++) {
-            char c = s.charAt(i);
-            if (Character.isDigit(c)) {
-                num = num * 10 + Character.getNumericValue(c);
-            }
-            
-            if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1){
-                if (sign == '-') {
-                    stack.push(-num);
-                }
-                else if (sign == '+') {
-                    stack.push(num);
-                }
-                else if (sign == '*') {
-                    stack.push(stack.pop() * num);
-                }
-                else {
-                    stack.push(stack.pop() / num);
-                }
-
-                sign = c;
-                num = 0;
-            }
+  public int calculate(String s) {
+    Stack<Integer> stack = new Stack<>();
+    int num = 0;
+    char sign = '+';
+    for (int i = 0; i < s.length(); i++) {
+      char c = s.charAt(i);
+      if (Character.isDigit(c)) {
+        num = num * 10 + Character.getNumericValue(c);
+      }
+      if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1) {
+        if (sign == '-') {
+          stack.push(-num);
         }
-
-        int res = 0;
-        while (!stack.isEmpty()) {
-            res += stack.pop();
+        else if (sign == '+') {
+          stack.push(num);
         }
-
-        return res;
+        else if (sign == '*') {
+          stack.push(stack.pop() * num);
+        }
+        else {
+          stack.push(stack.pop() / num);
+        }
+        sign = c;
+        num = 0;
+      }
+    }
+    int res = 0;
+    while (!stack.isEmpty()) {
+      res += stack.pop();
     }
+    return res;
+  }
 }
diff --git a/Medium/Boats to Save People.java b/Medium/Boats to Save People.java
@@ -1,19 +1,16 @@
 class Solution {
-    public int numRescueBoats(int[] people, int limit) {
-        Arrays.sort(people);
-        int count = 0;
-        int start = 0;
-        int end = people.length-1;
-        
-        while (end >= start) {
-            if (people[start] + people[end] <= limit) {
-                start++;
-            }
-            
-            end--;
-            count++;
-        }
-        
-        return count;
+  public int numRescueBoats(int[] people, int limit) {
+    Arrays.sort(people);
+    int count = 0;
+    int start = 0;
+    int end = people.length - 1;
+    while (end >= start) {
+      if (people[start] + people[end] <= limit) {
+        start++;
+      }
+      end--;
+      count++;
     }
+    return count;
+  }
 }
diff --git a/Medium/Delete Node in a BST.java b/Medium/Delete Node in a BST.java
@@ -4,54 +4,40 @@
  *     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 TreeNode deleteNode(TreeNode root, int key) {
-        if (root == null) {
-            return root;
-        }
-        
-        if (key < root.val) {
-            root.left = deleteNode(root.left, key);
-        }
-        else if (key > root.val) {
-            root.right = deleteNode(root.right, key);
-        }
-        else {
-            if (root.left == null || root.right == null) {
-                TreeNode temp = root.left == null ? root.right : root.left;
-                
-                if (temp == null) {
-                    return null;
-                }
-                else {
-                    return temp;
-                }
-            }
-            else {
-                TreeNode rightSuccessor = getRightSuccessor(root);
-                root.val = rightSuccessor.val;
-                root.right = deleteNode(root.right, rightSuccessor.val);
-            }
-        }
-        
-        return root;
+  public TreeNode deleteNode(TreeNode root, int key) {
+    if (root == null) {
+      return null;
     }
-    
-    private TreeNode getRightSuccessor(TreeNode node) {
-        if (node == null) {
-            return null;
-        }    
-        
-        TreeNode temp = node.right;
-        if (temp != null) {
-            while (temp.left != null) {
-                temp = temp.left;
-            }
-        }
-        
+    if (root.val > key) {
+      root.left = deleteNode(root.left, key);
+    }
+    else if (root.val < key) {
+      root.right = deleteNode(root.right, key);
+    }
+    else {
+      if (root.left == null || root.right == null) {
+        TreeNode temp = root.left == null ? root.right : root.left;
         return temp;
+      }
+      else {
+        TreeNode inorderSuccessor = root.right;
+        while (inorderSuccessor.left != null) {
+          inorderSuccessor = inorderSuccessor.left;
+        }
+        root.val = inorderSuccessor.val;
+        root.right = deleteNode(root.right, inorderSuccessor.val);
+      }
     }
+    return root;
+  }
 }
diff --git a/Medium/Linked List Cycle II.java b/Medium/Linked List Cycle II.java
@@ -10,23 +10,26 @@
  * }
  */
 public class Solution {
-    public ListNode detectCycle(ListNode head) {
-        ListNode slow = head;
-        ListNode fast = head;
-
-        while (fast!=null && fast.next!=null){
-            fast = fast.next.next;
-            slow = slow.next;
-
-            if (fast == slow){
-                ListNode slow2 = head; 
-                while (slow2 != slow){
-                    slow = slow.next;
-                    slow2 = slow2.next;
-                }
-                return slow;
-            }
-        }
-        return null;
+  public ListNode detectCycle(ListNode head) {
+    ListNode slow = head;
+    ListNode fast = head;
+    boolean cycle = false;
+    while (fast != null && fast.next != null) {
+      slow = slow.next;
+      fast = fast.next.next;
+      if (slow == fast) {
+        cycle = true;
+        break;
+      }
     }
+    if (!cycle) {
+      return null;
+    }
+    slow = head;
+    while (slow != fast) {
+      slow = slow.next;
+      fast = fast.next;
+    }
+    return slow;
+  }
 }
diff --git a/Medium/Longest Well-Performing Interval.java b/Medium/Longest Well-Performing Interval.java
@@ -1,27 +1,20 @@
 class Solution {
-    public int longestWPI(int[] hours) {
-        int ans = 0;
-        int[] preComputed = new int[hours.length + 1];
-        
-        for (int i = 1; i < preComputed.length; i++) {
-            if (hours[i - 1] > 8) {
-                ans = 1;
-                preComputed[i] = preComputed[i - 1] + 1;
-            }
-            else {
-                preComputed[i] = preComputed[i - 1] - 1;
-            }
-        }
-        
-        for(int i = 0; i <= hours.length; i++){
-            for(int j = hours.length; j > i; j--){
-                if(preComputed[j]-preComputed[i] > 0){
-                    ans = Math.max(ans, j - i);
-                    break;
-                }
-            }
-        }
-        
-        return ans;
+  public int longestWPI(int[] hours) {
+    int sum = 0;
+    int maxInterval = 0;
+    boolean greaterThanEightFound = false;
+    Map<Integer, Integer> map = new HashMap<>();
+    for (int i = 0; i < hours.length; i++) {
+      sum += hours[i] > 8 ? 1 : -1;
+      greaterThanEightFound = hours[i] > 8 ? true : greaterThanEightFound;
+      map.putIfAbsent(sum, i);
+      if (sum >= 1) {
+        maxInterval = Math.max(maxInterval, i + 1);
+      }
+      else if (map.containsKey(sum - 1)) {
+        maxInterval = Math.max(maxInterval, i - map.get(sum - 1));
+      }
     }
+    return maxInterval == 0 ? (greaterThanEightFound ? 1 : 0) : maxInterval;
+  }
 }
diff --git a/Medium/Rotate List.java b/Medium/Rotate List.java
@@ -3,54 +3,43 @@
  * public class ListNode {
  *     int val;
  *     ListNode next;
- *     ListNode(int x) { val = x; }
+ *     ListNode() {}
+ *     ListNode(int val) { this.val = val; }
+ *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  * }
  */
 class Solution {
-    
-    public void rotateArr(int[] arr) {
-        int temp = arr[0];
-        for (int i=1;i<arr.length;i++) {
-            int t = arr[i];
-            arr[i] = temp;
-            temp = t;
-        }
-        
-        arr[0] = temp;
+  public ListNode rotateRight(ListNode head, int k) {
+    if (head == null || head.next == null || k == 0) {
+      return head;
     }
-    
-    public ListNode rotateRight(ListNode head, int k) {
-        if (head == null || head.next == null || k == 0) return head;
-        int l = 0;
-        ListNode curr = head;
-        while (curr != null) {
-            curr = curr.next;
-            l++;
-        }
-        
-        int[] arr = new int[l];
-        curr = head;
-        
-        for (int i=0;i<l;i++) {
-            arr[i] = curr.val;
-            curr = curr.next;
-        }
-        
-        k = k%l;
-        
-        while (k > 0) {
-            rotateArr(arr);
-            k--;
-        }
-    
-        curr = head;
-        int j = 0;
-        while (curr != null) {
-            curr.val = arr[j];
-            j++;
-            curr = curr.next;
-        }
-        
-        return head;
+    ListNode curr = head;
+    // Get length of list & update the number of rotations
+    int count = 0;
+    while (curr != null) {
+      curr = curr.next;
+      count++;
     }
+    k %= count;
+    if (k == 0) {
+      return head;
+    }
+    // Move the pointer just before the rotation index
+    int stop = count - k;
+    int currCount = 1;
+    curr = head;
+    while (currCount < stop) {
+      currCount++;
+      curr = curr.next;
+    }
+    ListNode nextNode = curr.next;
+    // Detach rotation part of list and append it in the beginning of list
+    curr.next = null;
+    ListNode newHead = nextNode;
+    while (nextNode.next != null) {
+      nextNode = nextNode.next;
+    }
+    nextNode.next = head;
+    return newHead;
+  }
 }
