Added 4 solutions & modified 2 solutions

varunu28 · varunu28 · commit aac344141e61 · 2019-07-12T16:40:09.000-07:00
diff --git a/Concurrency/Print in Order.java b/Concurrency/Print in Order.java
@@ -0,0 +1,53 @@
+class Foo {
+    
+    private int counter = 1;
+    private String mutex = "";
+    public Foo() {
+        
+    }
+
+    public void first(Runnable printFirst) throws InterruptedException {
+        
+        // printFirst.run() outputs "first". Do not change or remove this line.
+        boolean flag = true;
+        while (flag) {
+            synchronized(mutex) {
+                if (counter == 1) {
+                    printFirst.run();
+                    counter++;
+                    flag = false;
+                }
+            }
+        }
+    }
+
+    public void second(Runnable printSecond) throws InterruptedException {
+        
+        // printSecond.run() outputs "second". Do not change or remove this line.
+        boolean flag = true;
+        while (flag) {
+            synchronized(mutex) {
+                if (counter == 2) {
+                    printSecond.run();
+                    counter++;
+                    flag = false;
+                }
+            }
+        }
+    }
+
+    public void third(Runnable printThird) throws InterruptedException {
+        
+        // printThird.run() outputs "third". Do not change or remove this line.
+        boolean flag = true;
+        while (flag) {
+            synchronized(mutex) {
+                if (counter == 3) {
+                    printThird.run();
+                    counter++;
+                    flag = false;
+                }
+            }
+        }
+    }
+}
diff --git a/Easy/Flood Fill.java b/Easy/Flood Fill.java
@@ -1,20 +1,20 @@
 class Solution {
+    public int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
     public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
-        int color = image[sr][sc];
-        if (color != newColor) {
-            dfs(image, sr, sc, color, newColor);
-        }
-        
+        dfs(image, sr, sc, newColor, image[sr][sc]);
         return image;
     }
     
-    public void dfs(int[][] image, int sr, int sc, int color, int newColor) {
-        if (image[sr][sc] == color) {
-            image[sr][sc] = newColor;
-            if (sr >= 1) dfs(image, sr-1, sc, color, newColor);
-            if (sc >= 1) dfs(image, sr, sc-1, color, newColor);
-            if (sr+1 < image.length) dfs(image, sr+1, sc, color, newColor);
-            if (sc+1 < image[0].length) dfs(image, sr, sc+1, color, newColor);
+    private void dfs(int[][] image, int x, int y, int newColor, int oldColor) {
+        if(x < 0 || x >= image.length || y < 0 || y >= image[0].length || image[x][y] == newColor) {
+            return;
         }
-    } 
+        
+        if (image[x][y] == oldColor) {
+            image[x][y] = newColor;
+            for (int[] dir : dirs) {
+                dfs(image, x + dir[0], y + dir[1], newColor, oldColor);
+            }
+        }
+    }
 }
diff --git a/Easy/Greatest Common Divisor of Strings.java b/Easy/Greatest Common Divisor of Strings.java
@@ -0,0 +1,36 @@
+class Solution {
+    public String gcdOfStrings(String str1, String str2) {
+        return stringGcd(str1, str2);
+    }
+    
+    private String stringGcd(String s1, String s2) {
+        if (s1.length() == 0) {
+            return s2;
+        }
+        
+        if (s2.length() == 0) {
+            return s1;
+        }
+        
+        if (s1.equals(s2)) {
+            return s1;
+        }
+        
+        if (s1.length() > s2.length()) {
+            for (int i = 0; i < s2.length(); i++) {
+                if (s1.charAt(i) != s2.charAt(i)) {
+                    return "";
+                }
+            }
+            
+            String temp = s1.substring(s2.length());
+            return stringGcd(temp, s2);
+        }
+        
+        if (s2.length() > s1.length()) {
+            return stringGcd(s2, s1);
+        }
+        
+        return "";
+    }
+}
diff --git a/Easy/Rotate String.java b/Easy/Rotate String.java
@@ -1,17 +1,9 @@
 class Solution {
     public boolean rotateString(String A, String B) {
-        if (A.isEmpty() && B.isEmpty()) return true;
-        int n = A.length();
-        int shiftCount = 0;
-        
-        while(shiftCount < n) {
-            if (A.equals(B)) {
-                return true;
-            }
-            A = A.substring(1, n) + A.substring(0,1);
-            shiftCount++;
+        if (A.length() != B.length()) {
+            return false;
         }
         
-        return false;
+        return (A + A).contains(B);
     }
 }
diff --git a/Medium/Insufficient Nodes in Root to Leaf Paths.java b/Medium/Insufficient Nodes in Root to Leaf Paths.java
@@ -0,0 +1,25 @@
+/**
+ * Definition for a binary tree node.
+ * public class TreeNode {
+ *     int val;
+ *     TreeNode left;
+ *     TreeNode right;
+ *     TreeNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public TreeNode sufficientSubset(TreeNode root, int limit) {
+        if (root == null) {
+            return null;
+        }
+        
+        if (root.left == null && root.right == null) {
+            return root.val < limit ? null : root;
+        }
+        
+        root.left = sufficientSubset(root.left, limit - root.val);
+        root.right = sufficientSubset(root.right, limit - root.val);
+        
+        return root.left == root.right ? null : root;
+    }
+}
diff --git a/Medium/Majority Element II.java b/Medium/Majority Element II.java
@@ -0,0 +1,56 @@
+class Solution {
+    public List<Integer> majorityElement(int[] nums) {
+        if (nums.length == 0) {
+            return new ArrayList<>();
+        }
+        
+        int num1 = nums[0];
+        int num2 = nums[0];
+        int count1 = 0;
+        int count2 = 0;
+        
+        for (int i = 0; i < nums.length; i++) {
+            if (nums[i] == num1) {
+                count1++;
+            }
+            else if (nums[i] == num2) {
+                count2++;
+            }
+            else if (count1 == 0) {
+                num1 = nums[i];
+                count1 = 1;
+            }
+            else if (count2 == 0) {
+                num2 = nums[i];
+                count2 = 1;
+            }
+            else {
+                count1--;
+                count2--;
+            }
+        }
+        
+        count1 = 0;
+        count2 = 0;
+        
+        for (int i = 0; i< nums.length; i++) {
+            if (nums[i] == num1) {
+                count1++;
+            }
+            else if (nums[i] == num2) {
+                count2++;
+            }
+        }
+        
+        List<Integer> ans = new ArrayList<>();
+        if (count1 > nums.length / 3) {
+            ans.add(num1);
+        }
+        
+        if (count2 > nums.length / 3) {
+            ans.add(num2);
+        }
+        
+        return ans;
+    }
+}
