Leetcode: Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

 
The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
Hints:If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        TreeNode runner = root;
        while(runner!=null){
            if(runner.left!=null){
                findRightMostChild(runner.left).right = runner.right;
                runner.right = runner.left;
                runner.left = null;
            }
            runner = runner.right;
        }
        
    }
    
    public TreeNode findRightMostChild(TreeNode node){
        while(node.right!=null){
            node = node.right;
        }
        return node;
    }
FacebookTwitterGoogle+Share

Leetcode: Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of everynode never differ by more than 1.

public boolean isBalanced(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(isBalancedHelper(root)==-1){
            return false;
        }else{
            return true;
        }
    }

    //return -1 if the two subtrees of this node is unbalanced
    //return the height of this node otherwise
    public int isBalancedHelper(TreeNode node){
        if(node==null){
            return 0;
        }else{
            int leftHeight = isBalancedHelper(node.left);
            int rightHeight = isBalancedHelper(node.right);
            if(leftHeight==-1 || rightHeight==-1){
                return -1;
            }
            if(Math.abs(leftHeight-rightHeight)<=1){
                return Math.max(leftHeight,rightHeight)+1;
            }else{
                return -1;
            }
        }
    }

Running time is O(n) since all the nodes are visited only once.

Leetcode: Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

public String addBinary(String a, String b) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int carry = 0;
        String sumStr = "";
        int i=a.length()-1;
        int j=b.length()-1;
        while(i>=0 || j>=0){
            int bitSum =0;
            if(i>=0 && j>=0){
                bitSum= Integer.parseInt(a.substring(i,i+1))+Integer.parseInt(b.substring(j,j+1)) + carry;
                i--;
                j--;
            }else if(i>=0){
                bitSum= Integer.parseInt(a.substring(i,i+1))+carry;
                i--;
            }else{
                bitSum= Integer.parseInt(b.substring(j,j+1)) + carry;
                j--;
            }
            carry = bitSum/2;
            int bit = bitSum%2;
            sumStr = bit+sumStr;    
        }
        if(carry==1){
            sumStr = carry+sumStr;
        }
        return sumStr;
    }

Leetcode: 4Sum

Given an array S of n integers, are there elements abc, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.

For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function

        ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
        HashSet<ArrayList<Integer>> resultSet = new HashSet<ArrayList<Integer>>();
        if(num.length<4){
            return output;
        }
        Arrays.sort(num);
        for(int i=0;i<num.length-3;i++){
            for(int j=i+1;j<num.length-2;j++){
                int k = j+1;
                int l = num.length-1;
                while(k<l){
                    int sum = num[i]+num[j]+num[k]+num[l];
                    if(sum==target){
                        ArrayList<Integer> result = new ArrayList<Integer>();
                        result.add(num[i]);
                        result.add(num[j]);
                        result.add(num[k]);
                        result.add(num[l]);
                        if(resultSet.add(result)){
                            output.add(result);
                        }
                        k++;
                        l--;
                    }else if(sum<target){
                        k++;
                    }else{
                        l--;
                    }
                }
            }
        }
        return output;

    }

O(N^3) time and O(n^3) space needed. Waiting for more efficient solutions.

Leetcode: 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
public int threeSumClosest(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int minDiff = Integer.MAX_VALUE;
        int bestSum = -1;
        Arrays.sort(num);
        for(int i=0;i<num.length;i++){
            int twoSum = findClosest(num,i,target);
            int sum = twoSum+num[i];
            if(Math.abs(sum-target)<minDiff){
                minDiff = Math.abs(sum-target);
                bestSum = sum;
            }
        }
        return bestSum;
    }

    public int findClosest(int[] num, int curr, int target){
        int newTarget = target-num[curr];
        int left = 0;
        if(left==curr){
            left++;
        }
        int right = num.length-1;
        if(right==curr){
            right--;
        }
        int minDiff = Integer.MAX_VALUE;
        int bestSum = -1;
        while(left<right){
            int sum = num[left]+num[right];
            if(sum==newTarget){
                return newTarget;
            }
            if(Math.abs(sum-newTarget)<minDiff){
                    minDiff = Math.abs(sum-newTarget);
                    bestSum = sum;
            }
            if(sum<newTarget){
                left++;
                if(left==curr){
                    left++;
                }
            }else{
                right--;
                if(right==curr){
                    right--;
                }
            }
        }
        return bestSum;
    }

The findClosest is a helper function which finds a pair of integers in the given array with the closest sum to the new target num. The new target number is target-num[curr]. Then in the main function, we only need to pick a number as the first integer among the three integers and then use this function to find the closest sum of the rest two integers.

We should first sort the array so that it only takes O(n) for findClosest each time. So the total running time is O(nlgn+n2) = O(n2).

Leetcode: Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int profit = 0;
    for (int i = 0; i < prices.length; i++) {
        if (i + 1 < prices.length && prices[i] < prices[i + 1]) {
            profit += prices[i + 1] - prices[i];
        }
    }
    return profit;
}