Accepted solutions

gouthampradhan · gouthampradhan · commit ea5e5391a8e6 · 2018-02-17T15:23:56.000+01:00
diff --git a/README.md b/README.md
@@ -36,6 +36,7 @@ My accepted leetcode solutions to some of the common interview problems.
 - [Next Greater Element I](problems/src/array/NextGreaterElementI.java) (Easy)
 - [Largest Number At Least Twice of Others](problems/src/array/LargestNumberAtLeastTwice.java) (Easy)
 - [Minimum Moves to Equal Array Elements II](problems/src/array/MinimumMovesToEqualArray.java) (Median)
+- [Image Smoother](problems/src/array/ImageSmoother.java) (Easy)
 
 #### [Backtracking](problems/src/backtracking)
 
@@ -290,6 +291,7 @@ My accepted leetcode solutions to some of the common interview problems.
 - [Same Tree](problems/src/tree/SameTree.java) (Easy)
 - [Binary Tree Longest Consecutive Sequence II](problems/src/tree/BinaryTreeLongestConsecutiveSequenceII.java) (Medium)
 - [Minimum Absolute Difference in BST](problems/src/tree/MinimumAbsoluteDifferenceInBST.java) (Medium)
+- [Equal Tree Partition](problems/src/tree/EqualTreePartition.java) (Medium)
 
 #### [Two Pointers](problems/src/two_pointers)
 
diff --git a/problems/src/array/ImageSmoother.java b/problems/src/array/ImageSmoother.java
@@ -0,0 +1,57 @@
+package array;
+/**
+ * Created by gouthamvidyapradhan on 17/02/2018.
+ *  * Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the
+ * gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself.
+ * If a cell has less than 8 surrounding cells, then use as many as you can.
+
+ Example 1:
+ Input:
+ [[1,1,1],
+ [1,0,1],
+ [1,1,1]]
+ Output:
+ [[0, 0, 0],
+ [0, 0, 0],
+ [0, 0, 0]]
+ Explanation:
+ For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
+ For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
+ For the point (1,1): floor(8/9) = floor(0.88888889) = 0
+ Note:
+ The value in the given matrix is in the range of [0, 255].
+ The length and width of the given matrix are in the range of [1, 150].
+ */
+
+public class ImageSmoother {
+
+    int[] R = {1, -1, 0, 0, 1, -1, 1, -1};
+    int[] C = {0, 0, -1, 1, 1, 1, -1, -1};
+    public static void main(String[] args) throws Exception{
+
+    }
+
+    public int[][] imageSmoother(int[][] M) {
+        int[][] result = new int[M.length][M[0].length];
+        for(int i = 0; i < M.length; i ++){
+            for(int j = 0; j < M[0].length; j ++){
+                int numCount = 0;
+                int totalCount = 1;
+                for(int k = 0; k < 8; k++){
+                    int newR = i + R[k];
+                    int newC = j + C[k];
+                    if(newR >= 0 && newC >= 0 && newR < M.length && newC < M[0].length){
+                        if(M[newR][newC] > 0){
+                            numCount += M[newR][newC];
+                        }
+                        totalCount++;
+                    }
+                }
+                if(M[i][j] == 1) numCount++;
+                result[i][j] = numCount / totalCount;
+            }
+        }
+        return result;
+    }
+
+}
diff --git a/problems/src/tree/EqualTreePartition.java b/problems/src/tree/EqualTreePartition.java
@@ -0,0 +1,95 @@
+package tree;
+
+/**
+ * Created by gouthamvidyapradhan on 17/02/2018.
+ * Given a binary tree with n nodes, your task is to check if it's possible to partition the tree to two trees which
+ * have the equal sum of values after removing exactly one edge on the original tree.
+
+ Example 1:
+ Input:
+ 5
+ / \
+ 10 10
+ /  \
+ 2   3
+
+ Output: True
+ Explanation:
+ 5
+ /
+ 10
+
+ Sum: 15
+
+ 10
+ /  \
+ 2    3
+
+ Sum: 15
+ Example 2:
+ Input:
+ 1
+ / \
+ 2  10
+ /  \
+ 2   20
+
+ Output: False
+ Explanation: You can't split the tree into two trees with equal sum after removing exactly one edge on the tree.
+ Note:
+ The range of tree node value is in the range of [-100000, 100000].
+ 1 <= n <= 10000
+ */
+
+public class EqualTreePartition {
+    public class TreeNode {
+        int val;
+        TreeNode left;
+        TreeNode right;
+        TreeNode(int x) { val = x; }
+    }
+    private long sum;
+    private boolean possible = false;
+
+    public static void main(String[] args) throws Exception{
+
+    }
+
+    public boolean checkEqualTree(TreeNode root) {
+        sum = 0L;
+        getSum(root);
+        getDiff(root);
+        return possible;
+    }
+
+    private void getSum(TreeNode node){
+        if(node != null){
+            sum += node.val;
+            getSum(node.left);
+            getSum(node.right);
+        }
+    }
+
+    private Long getDiff(TreeNode node){
+        if(node == null) return null;
+        Long left = getDiff(node.left);
+        Long right = getDiff(node.right);
+        if(left != null){
+            if((sum - left) == left){
+                possible = true;
+            }
+        }if(right != null){
+            if((sum - right) == right){
+                possible = true;
+            }
+        }
+        Long curr = (long)node.val;
+        if(left != null){
+            curr += left;
+        } if(right != null){
+            curr += right;
+        }
+        return curr;
+    }
+
+}
