Added 4 solutions

varunu28 · varunu28 · commit 098c75aa05d2 · 2019-07-15T19:45:53.000-07:00
diff --git a/Hard/Number of Submatrices That Sum to Target.java b/Hard/Number of Submatrices That Sum to Target.java
@@ -0,0 +1,29 @@
+class Solution {
+    public int numSubmatrixSumTarget(int[][] matrix, int target) {
+        int rows = matrix.length;
+        int cols = matrix[0].length;
+        int res = 0;
+        
+        for (int i = 0; i < rows; i++) {
+            for (int j = 1; j < cols; j++) {
+                matrix[i][j] += matrix[i][j - 1];
+            }
+        }
+        
+        for (int i = 0; i < cols; i++) {
+            for (int j = i; j < cols; j++) {
+                Map<Integer, Integer> map = new HashMap<>();
+                map.put(0, 1);
+                int sum = 0;
+                for (int k = 0; k < rows; k++) {
+                    sum += matrix[k][j] - (i > 0 ? matrix[k][i - 1] : 0);
+                    res += map.getOrDefault(sum - target, 0);
+                    
+                    map.put(sum, map.getOrDefault(sum, 0) + 1);
+                }
+            }
+        }
+        
+        return res;
+    }
+}
diff --git a/Medium/Missing Element in Sorted Array.java b/Medium/Missing Element in Sorted Array.java
@@ -0,0 +1,26 @@
+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;
+    }
+}
diff --git a/Medium/Range Sum Query - Mutable.java b/Medium/Range Sum Query - Mutable.java
@@ -0,0 +1,71 @@
+class NumArray {
+    int[] fen;
+    int[] nums;
+    int n;
+    public NumArray(int[] nums) {
+        this.nums = nums;
+        n = nums.length;
+        fen = new int[n + 1];
+        init();
+    }
+
+    private void init () {
+        if (n == 0) {
+            return;
+        }
+
+        // Compute the pre-sum
+        fen[1] = nums[0];
+        for (int i = 1; i < n; i++) {
+            fen[i + 1] = fen[i] + nums[i];
+        }
+
+        for (int i = n; i > 0; i--) {
+            // Removing the value of parent for each node
+            int parent = i - (i & -i);
+            if (parent >= 0) {
+                fen[i] -= fen[parent];
+            }
+        }
+    }
+
+    public void update(int i, int val) {
+        // Find the difference between previous and current value
+        int extra = val - nums[i];
+
+        // Update the actual array with the new val
+        nums[i] = val;
+
+        // Update the tree with the extra value to all the parents 
+        increment(i, extra);
+    }
+
+    private void increment (int i, int extra) {
+        i++;
+        while (i <= n) {
+            fen[i] += extra;
+            i = i + (i & -i);
+        }
+    }
+
+    public int sumRange(int i, int j) {
+        // Similar to pre sum from 0 to j - pre sum from 0 to i
+        return getSum(j + 1) - getSum(i);
+    }
+
+    private int getSum (int i) {
+        int res = 0;
+        while (i > 0) {
+            res += fen[i];
+            i = i - (i & -i);
+        }
+
+        return res;
+    }
+}
+/**
+ * Your NumArray object will be instantiated and called as such:
+ * NumArray obj = new NumArray(nums);
+ * obj.update(i,val);
+ * int param_2 = obj.sumRange(i,j);
+ */
diff --git a/Medium/Uncrossed Lines.java b/Medium/Uncrossed Lines.java
@@ -0,0 +1,25 @@
+class Solution {
+    public int maxUncrossedLines(int[] A, int[] B) {
+        Integer[][] dp = new Integer[A.length][B.length];
+        return helper(A, 0, B, 0, dp);
+    }
+    
+    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];
+    }
+}
