Added 1 solution & modified 3 solutions

varunu28 · varunu28 · commit 353e58de64c8 · 2020-08-03T19:30:18.000-05:00
diff --git a/Medium/Maximum of Absolute Value Expression.java b/Medium/Maximum of Absolute Value Expression.java
@@ -0,0 +1,18 @@
+class Solution {
+  public int maxAbsValExpr(int[] arr1, int[] arr2) {
+    int res = 0;
+    int n = arr1.length;
+    int[] dirs = {-1,1};
+    for (int dir1 : dirs) {
+      for (int dir2 : dirs) {
+        int closest = dir1 * arr1[0] + dir2 * arr2[0] + 0;
+        for (int i = 1; i < n; ++i) {
+          int cur = dir1 * arr1[i] + dir2 * arr2[i] + i;
+          res = Math.max(res, cur - closest);
+          closest = Math.min(closest, cur);
+        }
+      }
+    }
+    return res;
+  }
+}
diff --git a/Medium/Missing Element in Sorted Array.java b/Medium/Missing Element in Sorted Array.java
@@ -1,26 +1,24 @@
 class Solution {
-    public int missingElement(int[] nums, int k) {
-        int idx = 0;
-        while (idx < nums.length - 1) {
-            if (nums[idx] != nums[idx + 1] - 1) {
-                int diff = nums[idx + 1] - nums[idx] - 1;
-                if (diff >= k) {
-                    int step = nums[idx] + 1;
-                    while (k > 1) {
-                        step++;
-                        k--;
-                    }
-                    
-                    return step;
-                }
-                else {
-                    k -= diff;
-                }
-            }
-            
-            idx++;
-        }
-        
-        return nums[nums.length - 1] + k;
+  public int missingElement(int[] nums, int k) {
+    int n = nums.length;
+    if (k > missing(n - 1,  nums)) {
+      return nums[n - 1] + k - missing(n - 1, nums);
     }
+    int start = 0;
+    int end = n - 1;
+    while (start < end) {
+      int mid = start + (end - start) / 2;
+      if (missing(mid, nums) < k) {
+        start = mid + 1;
+      }
+      else {
+        end = mid;
+      }
+    }
+    return nums[start - 1] + k - missing(start - 1, nums);
+  }
+  
+  private int missing(int idx, int[] nums) {
+    return nums[idx] - nums[0] - idx;
+  }
 }
diff --git a/Medium/Palindromic Substrings.java b/Medium/Palindromic Substrings.java
@@ -1,20 +1,16 @@
 class Solution {
-    public int countSubstrings(String s) {
-        int count = 0;
-        for (int i=0;i<s.length();i++) {
-            for (int j=i;j<s.length();j++) {
-                if(isPalindrome(s.substring(i,j+1))) {
-                    count++;
-                }
-            }
+  public int countSubstrings(String s) {
+    int N = s.length();
+    int ans = 0;
+    for (int center = 0; center <= 2 * N - 1; ++center) {
+        int left = center / 2;
+        int right = left + center % 2;
+        while (left >= 0 && right < N && s.charAt(left) == s.charAt(right)) {
+            ans++;
+            left--;
+            right++;
         }
-        
-        return count;
-    }
-    
-    public boolean isPalindrome(String s) {
-        StringBuilder sb = new StringBuilder("");
-        sb.append(s);
-        return sb.reverse().toString().equals(s);
     }
+    return ans;
+  }
 }
diff --git a/Medium/Uncrossed Lines.java b/Medium/Uncrossed Lines.java
@@ -1,25 +1,23 @@
 class Solution {
-    public int maxUncrossedLines(int[] A, int[] B) {
-        Integer[][] dp = new Integer[A.length][B.length];
-        return helper(A, 0, B, 0, dp);
+  Integer[][] dp;
+  public int maxUncrossedLines(int[] A, int[] B) {
+    dp = new Integer[A.length][B.length];
+    return helper(A, 0, B, 0);
+  } 
+  
+  private int helper(int[] A, int idxA, int[] B, int idxB) {
+    if (idxA == A.length || idxB == B.length) {
+      return 0;
+    } 
+    if (dp[idxA][idxB] != null) {
+      return dp[idxA][idxB];
     }
-    
-    private int helper(int[] A, int i, int[] B, int j, Integer[][] dp) {
-        if (i >= A.length || j >= B.length) {
-            return 0;
-        }
-        
-        if (dp[i][j] != null) {
-            return dp[i][j];
-        }
-        
-        if (A[i] == B[j]) {
-            dp[i][j] = 1 + helper(A, i + 1, B, j + 1, dp);
-        }
-        else {
-            dp[i][j] = Math.max(helper(A, i + 1, B, j, dp), helper(A, i, B, j + 1, dp));
-        }
-        
-        return dp[i][j];
+    if (A[idxA] == B[idxB]) {
+      dp[idxA][idxB] = 1 + helper(A, idxA + 1, B, idxB + 1);
     }
+    else {
+      dp[idxA][idxB] = Math.max(helper(A, idxA + 1, B, idxB), helper(A, idxA, B, idxB + 1));
+    }
+    return dp[idxA][idxB];
+  }
 }
