Modified 2 solutions

varunu28 · varunu28 · commit 897a32d2ebb6 · 2019-07-17T23:34:13.000-07:00
diff --git a/Easy/Search Insert Position.java b/Easy/Search Insert Position.java
@@ -1,26 +1,25 @@
 class Solution {
     public int searchInsert(int[] nums, int target) {
-        int low = 0;
-        int high = nums.length-1;
-        
-        if (nums[low] >= target) {
-            return 0;
-        }
-        
-        if (nums[high] < target) {
-            return high + 1;
-        }
+        return binarySearch(nums, target);
+    }
+    
+    private int binarySearch(int[] nums, int target) {
+        int left = 0;
+        int right = nums.length - 1;
         
-        while (low < high) {
-            int mid = (low + high)/2;
-            if (nums[mid] < target) {
-                low = mid+1;
+        while (left <= right) {
+            int mid = (left + right) / 2;
+            if (nums[mid] == target) {
+                return mid;
+            }
+            else if (nums[mid] > target) {
+                right = mid - 1;
             }
             else {
-                high = mid;
+                left = mid + 1;
             }
         }
         
-        return low;
+        return left;
     }
 }
diff --git a/Medium/Friend Circles.java b/Medium/Friend Circles.java
@@ -1,41 +1,44 @@
 class Solution {
     public int findCircleNum(int[][] M) {
-        Map<Integer, List<Integer>> map = new HashMap<>();
-        for (int i=0; i<M.length; i++) {
-            for (int j=0; j<M[i].length; j++) {
+        Map<Integer, Set<Integer>> map = new HashMap<>();
+        for (int i = 0; i < M.length; i++) {
+            for (int j = 0; j < M.length; j++) {
                 if (M[i][j] == 1) {
-                    map.computeIfAbsent(i, k -> new ArrayList<>()).add(j);
-                    map.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
+                    map.computeIfAbsent(i, k -> new HashSet<>()).add(j);
                 }
             }
         }
-
-        Set<Integer> set = new HashSet<>();
+        
+        return dfs(map, M.length);
+    }
+    
+    private int dfs(Map<Integer, Set<Integer>> map, int n) {
         int count = 0;
-        Queue<Integer> queue = new LinkedList<>();
-
-        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
-            if (set.contains(entry.getKey())) {
-                continue;
+        Set<Integer> seen = new HashSet<>();
+        
+        for (int i = 0; i < n; i++) {
+            if (!seen.contains(i)) {
+                dfsHelper(i, seen, map);
+                count++;
             }
-
-            queue.add(entry.getKey());
-
-            while (!queue.isEmpty()) {
-                int popped = queue.remove();
-                set.add(popped);
-                List<Integer> list = map.get(popped);
-
-                for (Integer integer : list) {
-                    if (!set.contains(integer)) {
-                        queue.add(integer);
-                    }
+        }
+        
+        return count;
+    }
+    
+    private void dfsHelper(int idx, Set<Integer> seen, Map<Integer, Set<Integer>> map) {
+        Queue<Integer> queue = new LinkedList<>();
+        queue.add(idx);
+        
+        while (!queue.isEmpty()) {
+            int removed = queue.remove();
+            seen.add(removed);
+            
+            for (int friend : map.getOrDefault(removed, new HashSet<>())) {
+                if (!seen.contains(friend)) {
+                    queue.add(friend);
                 }
             }
-
-            count++;
         }
-
-        return count;
     }
 }
