Modified 2 solutions

varunu28 · varunu28 · commit 68ed6210cf9b · 2019-07-10T20:56:07.000-07:00
diff --git a/Hard/First Missing Positive.java b/Hard/First Missing Positive.java
@@ -1,19 +1,34 @@
 class Solution {
     public int firstMissingPositive(int[] nums) {
-        Set<Integer> set = new HashSet<>();
-        int max = 0;
+        int i = 0;
+        int n = nums.length;
+        while (i < n) {
+            // If in range 0..n & not in correct index then swap
+            if (nums[i] >= 0 && nums[i] < n && nums[nums[i]] != nums[i]) {
+                swap(nums, i, nums[i]);
+            }
+            else {
+                i++;
+            }
+        }
 
-        for (int num : nums) {
-            set.add(num);
-            max = Math.max(max, num);
+        int k = 1;
+        // Keep incrementing until the values are its correct position
+        while (k < n && nums[k] == k) {
+            k++;
         }
 
-        for (int i = 1; i <= max; i++) {
-            if (!set.contains(i)) {
-                return i;
-            }
+        // If empty array or k breaks between the end of the array
+        if (n == 0 || k < n) {
+            return k;
         }
+        
+        return nums[0] == k ? k + 1 : k;
+    }
 
-        return max + 1;
+    private void swap (int[] nums, int i, int num) {
+        int temp = nums[i];
+        nums[i] = nums[num];
+        nums[num] = temp;
     }
 }
diff --git a/Medium/Number of Islands.java b/Medium/Number of Islands.java
@@ -1,29 +1,41 @@
 class Solution {
+    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
     public int numIslands(char[][] grid) {
-        int count = 0;
+        if (grid.length == 0 || grid[0].length == 0) {
+            return 0;
+        }
+        
+        int countOfIslands = 0;
+        boolean[][] visited = new boolean[grid.length][grid[0].length];
+        int numOfRows = grid.length;
+        int numOfCols = grid[0].length;
         
-        for (int i=0; i<grid.length; i++) {
-            for (int j=0; j<grid[i].length; j++) {
-                if (grid[i][j] == '1') {
-                    count++;
-                    
-                    markArea(grid, i, j);
+        for (int i = 0; i < numOfRows; i++) {
+            for (int j = 0; j < numOfCols; j++) {
+                if (visited[i][j] || grid[i][j] == '0') {
+                    continue;
                 }
+                
+                dfs(grid, i, j, numOfRows, numOfCols, visited);
+                countOfIslands++;
             }
         }
         
-        return count;
+        return countOfIslands;
     }
     
-    private void markArea(char[][] grid, int i, int j) {
-        if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == '0') {
+    private void dfs(char[][] grid, int x, int y, int numOfRows, int numOfCols, boolean[][] visited) {
+        if (x < 0 || x >= numOfRows || y < 0 || y >= numOfCols || visited[x][y]) {
+            return;
+        }
+        
+        visited[x][y] = true;
+        if (grid[x][y] == '0') {
             return;
         }
         
-        grid[i][j] = '0';
-        markArea(grid, i-1, j);
-        markArea(grid, i, j-1);
-        markArea(grid, i, j+1);
-        markArea(grid, i+1, j);
+        for (int[] dir : dirs) {
+            dfs(grid, x + dir[0], y + dir[1], numOfRows, numOfCols, visited);
+        }
     }
 }
