Modified 4 solutions

varunu28 · varunu28 · commit 337907b70a17 · 2019-12-25T08:39:06.000+05:30
diff --git a/Easy/Remove Duplicates From Sorted Lists.java b/Easy/Remove Duplicates From Sorted Lists.java
@@ -7,23 +7,16 @@
  * }
  */
 class Solution {
-    public ListNode deleteDuplicates(ListNode head) {
-        if (head == null) return head;
-        ListNode copyHead = head;
-        while (head.next != null) {
-            if (head.val == head.next.val) {
-                if(head.next.next == null) {
-                    head.next = null;
-                    break;
-                }
-                else {
-                    head.next = head.next.next;
-                }
-            }
-            else {
-                head = head.next;
-            }
-        }
-        return copyHead;
+  public ListNode deleteDuplicates(ListNode head) {
+    ListNode curr = head;
+    while (curr != null) {
+      if (curr.next != null && curr.val == curr.next.val) {
+        curr.next = curr.next.next;
+      }
+      else {
+        curr = curr.next;
+      }
     }
+    return head;
+  }
 }
diff --git a/Medium/Remove Duplicates from Sorted List II.java b/Medium/Remove Duplicates from Sorted List II.java
@@ -7,26 +7,30 @@
  * }
  */
 class Solution {
-    public ListNode deleteDuplicates(ListNode head) {
-        if(head==null) return null;
-        
-        ListNode FakeHead=new ListNode(0);
-        FakeHead.next=head;
-        ListNode pre=FakeHead;
-        ListNode cur=head;
-        
-        while(cur!=null){
-            while(cur.next!=null&&cur.val==cur.next.val){
-                cur=cur.next;
-            }
-            if(pre.next==cur){
-                pre=pre.next;
-            }
-            else{
-                pre.next=cur.next;
-            }
-            cur=cur.next;
-        }
-        return FakeHead.next;
+  public ListNode deleteDuplicates(ListNode head) {
+    ListNode dummy = new ListNode(0);
+    dummy.next = head;
+    ListNode prev = dummy;
+    ListNode curr = head;
+    while (curr != null) {
+      int val = curr.val;
+      int count = 0;
+      ListNode temp = curr;
+      // Track the number of occurrences of value of current node
+      while (temp != null && temp.val == val) {
+        temp = temp.next;
+        count++;
+      }
+      // Update prev.next to the temp which can be a null or node with different value
+      if (count > 1) {
+        prev.next = temp;
+        curr = temp;
+      }
+      else {
+        prev = curr;
+        curr = curr.next;
+      }
     }
+    return dummy.next;
+  }
 }
diff --git a/Medium/Set Matrix Zeroes.java b/Medium/Set Matrix Zeroes.java
@@ -1,64 +1,57 @@
 class Solution {
-    public void setZeroes(int[][] arr) {
-        if (arr.length == 0 || arr[0].length == 0) {
-            return;
-        }
-
-
-        int numOfRows = arr.length;
-        int numOfCols = arr[0].length;
-        boolean firstRowZero = false;
-        boolean firstColZero = false;
-
-        for (int i = 0; i < numOfCols; i++) {
-            if (arr[0][i] == 0) {
-                firstRowZero = true;
-                break;
-            }
-        }
-
-        for (int i = 0; i < numOfRows; i++) {
-            if (arr[i][0] == 0) {
-                firstColZero = true;
-                break;
-            }
-        }
-
-        for (int i = 1; i < numOfRows; i++) {
-            for (int j = 0; j < numOfCols; j++) {
-                if (arr[i][j] == 0) {
-                    arr[0][j] = 0;
-                    arr[i][0] = 0;
-                }
-            }
-        }
-
-        for (int i = 1; i < numOfRows; i++) {
-            if (arr[i][0] == 0) {
-                for (int j = 1; j < numOfCols; j++) {
-                    arr[i][j] = 0;
-                }
-            }
-        }
-
-        for (int i = 0; i < numOfCols; i++) {
-            if (arr[0][i] == 0) {
-                for (int j = 1; j < numOfRows; j++) {
-                    arr[j][i] = 0;
-                }
-            }
-        }
-
-        if (firstRowZero) {
-            for (int i = 0; i < numOfCols; i++) {
-                arr[0][i] = 0;
-            }
+  public void setZeroes(int[][] matrix) {
+    boolean firstRowZero = false;
+    boolean firstColZero = false;
+    int numRows = matrix.length;
+    int numCols = matrix[0].length;
+    // Mark if first column needs to be set zero
+    for (int i = 0; i < numRows; i++) {
+      if (matrix[i][0] == 0) {
+        firstColZero = true;
+      }
+    }
+    // Mark if first row needs to be set zero
+    for (int i = 0; i < numCols; i++) {
+      if (matrix[0][i] == 0) {
+        firstRowZero = true;
+      }
+    }
+    // If a value in matrix is zero set the value at first row and column to be zero
+    for (int i = 1; i < numRows; i++) {
+      for (int j = 1; j < numCols; j++) {
+        if (matrix[i][j] == 0) {
+          matrix[0][j] = 0;
+          matrix[i][0] = 0;
+        }
+      }
+    }
+    // Update the complete column to be zero if first item of row is zero
+    for (int i = 1; i < numRows; i++) {
+      if (matrix[i][0] == 0) {
+        for (int j = 1; j < numCols; j++) {
+          matrix[i][j] = 0;
         }
-
-        if (firstColZero) {
-            for (int i = 0; i < numOfRows; i++) {
-                arr[i][0] = 0;
-            }
+      }
+    }
+    // Update the complete row to be zero if first item of column is zero
+    for (int i = 1; i < numCols; i++) {
+      if (matrix[0][i] == 0) {
+        for (int j = 1; j < numRows; j++) {
+          matrix[j][i] = 0;
         }
+      } 
+    }
+    // Set the first row to zero if flag is set
+    if (firstRowZero) {
+      for (int i = 0; i < numCols; i++) {
+        matrix[0][i] = 0;
+      }
+    }
+    // Set the first column to zero if flag is set
+    if (firstColZero) {
+      for (int i = 0; i < numRows; i++) {
+        matrix[i][0] = 0;
+      }
     }
+  }
 }
diff --git a/Medium/Unique Paths.java b/Medium/Unique Paths.java
@@ -1,22 +1,21 @@
 class Solution {
-
-    public int uniquePaths(int m, int n) {
-        int[][] arr = new int[m][n];
-        return getCount(arr, m, n);        
+  Integer[][] dp;
+  public int uniquePaths(int m, int n) {
+    dp = new Integer[m][n];
+    return dfs(m, n, 0, 0);
+  }
+  
+  private int dfs(int m, int n, int x, int y) {
+    if (x >= m || y >= n) {
+      return 0;
     }
-    
-    private int getCount(int[][] arr, int m, int n) {
-        for (int i=0; i<arr.length; i++) {
-            for (int j=0; j<arr[0].length; j++) {
-                if (i == 0 || j ==0) {
-                    arr[i][j] = 1;
-                }
-                else {
-                    arr[i][j] = arr[i-1][j] + arr[i][j-1];
-                }
-            }
-        }
-        
-        return arr[m-1][n-1];
+    if (dp[x][y] != null) {
+      return dp[x][y];
     }
+    if (x == m - 1 && y == n - 1) {
+      return 1;
+    }
+    dp[x][y] = dfs(m, n, x + 1, y) + dfs(m, n, x, y + 1);
+    return dp[x][y];
+  }
 }
