Added Sequential Digits.java & modified 2 solutions

varunu28 · varunu28 · commit e1451006bb78 · 2019-12-23T07:42:36.000+05:30
diff --git a/Easy/Rotting Oranges.java b/Easy/Rotting Oranges.java
@@ -1,48 +1,39 @@
 class Solution {
-    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
-    public int orangesRotting(int[][] grid) {
-        Queue<Integer> queue = new LinkedList<>();
-        Map<Integer, Integer> map = new HashMap<>();
-        int numRows = grid.length;
-        int numCols = grid[0].length;
-
-        for (int i = 0; i < numRows; i++) {
-            for (int j = 0; j < numCols; j++) {
-                if (grid[i][j] == 2) {
-                    int key = numCols * i + j;
-                    queue.add(key);
-                    map.put(key, 0);
-                }
-            }
+  int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
+  public final int VISITED = -1;
+  public int orangesRotting(int[][] grid) {
+    int minutes = 0;
+    Queue<int[]> queue = new LinkedList<>();
+    for (int i = 0; i < grid.length; i++) {
+      for (int j = 0; j < grid[i].length; j++) {
+        if (grid[i][j] == 2) {
+          queue.add(new int[]{i, j});
         }
-
-        int ans = 0;
-        while (!queue.isEmpty()) {
-            int key = queue.remove();
-            int x = key / numCols;
-            int y = key % numCols;
-            for (int[] dir : dirs) {
-                int newX = x + dir[0];
-                int newY = y + dir[1];
-                if (newX < 0 || newX >= numRows || newY < 0 || newY >= numCols || grid[newX][newY] != 1) {
-                    continue;
-                }
-                grid[newX][newY] = 2;
-                int newKey = newX * numCols + newY;
-                queue.add(newKey);
-                map.put(newKey, map.get(key) + 1);
-                ans = map.get(newKey);
-            }
+      }
+    }
+    while (!queue.isEmpty()) {
+      int size = queue.size();
+      while (size-- > 0) {
+        int[] removed = queue.remove();
+        for (int[] dir : dirs) {
+          int newX = removed[0] + dir[0];
+          int newY = removed[1] + dir[1];
+          if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 1) {
+            grid[newX][newY] = 2;
+            queue.add(new int[]{newX, newY});
+          }
         }
-
-        for (int i = 0; i < numRows; i++) {
-            for (int j = 0; j < numCols; j++) {
-                if (grid[i][j] == 1) {
-                    return -1;
-                }
-            }
+        grid[removed[0]][removed[1]] = VISITED;
+      }
+      minutes++;
+    }
+    for (int i = 0; i < grid.length; i++) {
+      for (int j = 0; j < grid[i].length; j++) {
+        if (grid[i][j] == 1) {
+          return -1;
         }
-
-        return ans;
+      }
     }
+    return minutes > 0 ? minutes - 1 : 0;
+  }
 }
diff --git a/Medium/Sequential Digits.java b/Medium/Sequential Digits.java
@@ -0,0 +1,18 @@
+class Solution {
+  public List<Integer> sequentialDigits(int low, int high) {
+    String bucket = "123456789";
+    int n = 10;
+    List<Integer> list = new ArrayList<>();
+    int lowLength = String.valueOf(low).length();
+    int highLength = String.valueOf(high).length();
+    for (int length = lowLength; length < highLength + 1; length++) {
+      for (int start = 0; start < n - length; start++) {
+        int num = Integer.parseInt(bucket.substring(start, start + length));
+        if (num >= low && num <= high) {
+          list.add(num);
+        }
+      }
+    }
+    return list;
+  }
+}
diff --git a/Medium/Summary Ranges.java b/Medium/Summary Ranges.java
@@ -1,45 +1,18 @@
 class Solution {
-    public List<String> summaryRanges(int[] nums) {
-        List<String> ranges = new ArrayList<>();
-
-        if (nums.length == 0) {
-            return ranges;
-        }
-
-        int count = 1;
-        int i = 0;
-        StringBuilder sb = new StringBuilder();
-        sb.append(nums[0]);
-        int n = nums.length-1;
-
-        while (i < n) {
-            if (nums[i+1] - nums[i] == 1) {
-                count++;
-            }
-            else {
-                if (count > 1) {
-                    sb.append("->").append(nums[i]);
-                    ranges.add(sb.toString());
-                    count = 1;
-                }
-                else {
-                    ranges.add(sb.toString());
-                }
-                sb = new StringBuilder();
-                sb.append(nums[i+1]);
-            }
-
-            i++;
-        }
-
-        if (count > 1) {
-            sb.append("->").append(nums[i]);
-            ranges.add(sb.toString());
-        }
-        else {
-            ranges.add(sb.toString());
-        }
-
-        return ranges;
+  public List<String> summaryRanges(int[] nums) {
+    List<String> list = new ArrayList<>();
+    int idx = 0;
+    int n = nums.length;
+    while (idx < n) {
+      int start = nums[idx];
+      int prev = start;
+      idx++;
+      while (idx < n && nums[idx] - prev == 1) {
+        prev = nums[idx];
+        idx++;
+      }
+      list.add(start == prev ? String.valueOf(start) : String.valueOf(start + "->" + prev));
     }
+    return list;
+  }
 }
