Flatten Binary Tree to Linked List

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

Pre-order Traversal

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (root == null) return;
        Stack stack = new Stack();
        stack.push(root);
        TreeNode lastNode = null;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (lastNode != null) {
                lastNode.left = null;
                lastNode.right = node;
            }
            lastNode = node;
            TreeNode left = node.left;
            TreeNode right = node.right;
            if (right != null) {
                stack.push(right);
            }
            if (left != null) {
                stack.push(left);
            }
        }
    }
}

Palindrome Number

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

Be aware of overflow problem.

class Solution {
public:
    bool isPalindrome(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (x < 0) return false;
        int digits = 1;
        int tester = 1;
        while (x / tester >= 10) {
            tester*=10;
            digits++;
        }
        
        while (x > 0) {
            if (x / tester == x % 10) {
                x -= x / tester * tester;
                x /= 10;
                tester /= 100;
            }
            else {
                return false;
            }
        }
        return true;
    }
};

4 Sum

4Sum

Given an array S of n integers, are there elements a, b, c, 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 class Solution {
    public ArrayList> fourSum(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        for (int i = 0; i < num.length - 3; i++) {
            int a = num[i];
            for (int j = i + 1; j < num.length - 2; j++) {
                int b = num[j];
                int k = j + 1;
                int l = num.length - 1;
                while (k < l) {
                    int c = num[k];
                    int d = num[l];
                    if (a + b + c + d == target) {
                        ArrayList sublist = new ArrayList();
                        sublist.add(a);
                        sublist.add(b);
                        sublist.add(c);
                        sublist.add(d);
                        list.add(sublist);
                        k++;
                        while (num[k] == num[k - 1] && k - 1 != j && k < l) {
                            k++;
                        }
                        l--;
                        while (num[l] == num[l + 1] && k < l) {
                            l--;
                        } 
                    }
                    else if (a + b + c + d < target) {
                        k++;
                        while (num[k] == num[k - 1] && k - 1 != j && k < l) {
                            k++;
                        }
                    }
                    else {
                        l--;
                        while (num[l] == num[l + 1] && k < l) {
                            l--;
                        } 
                    }
                }
                
                while (j + 1 < num.length - 2 && num[j + 1] == num[j]) {
                    j++;
                }
            }
            
            while (i + 1 < num.length - 3 && num[i + 1] == num[i]) {
                i++;
            }
        }
        
        return list;
    }
}

3 Sum Closest

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 class Solution {
    public int threeSumClosest(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList> list = new ArrayList>();
        
        Integer closest = null;
        
        for (int i = 0; i <= num.length - 3; i++) {
            int a = num[i];
            int j = i+1;
            int k = num.length - 1;
            if (closest == null) closest = a + num[j] + num[k];
            
            int best = closest.intValue();
            
            while (j < k) {
                int b = num[j];
                int c = num[k];
                if (a + b + c == target) {
                    return a + b + c;
                }
                else if (a + b + c < target) {
                    if (Math.abs(a + b + c - target)
                        < Math.abs(best - target)) {
                        best = a + b + c;
                    }
                    j++;
                }
                else {
                    if (Math.abs(a + b + c - target)
                        < Math.abs(best - target)) {
                        best = a + b + c;
                    }
                    k--;
                }
            }
            
            if (Math.abs(best - target) < Math.abs(closest.intValue() - target)) {
                closest = best;
            }
        }
        
        return closest.intValue();
    }
    
}

3 Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

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

    For example, given array S = {-1 0 1 2 -1 -4},

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

public class Solution {
    public ArrayList> threeSum(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        for (int i = 0; i <= num.length - 3; i++) {
            int a = num[i];
            int j = i+1;
            int k = num.length - 1;
            while (j < k) {
                int b = num[j];
                int c = num[k];
                if (a + b + c == 0) {
                    ArrayList sublist = new ArrayList();
                    sublist.add(a);
                    sublist.add(b);
                    sublist.add(c);
                    list.add(sublist);
                    j++;
                    while (num[j] == num[j - 1] && j - 1 != i && j < k) {
                        j++;
                    }
                    k--;
                    while (num[k] == num[k + 1] && j < k) {
                        k--;
                    } 
                }
                else if (a + b + c < 0) {
                    j++;
                    while (num[j] == num[j - 1] && j - 1 != i && j < k) {
                        j++;
                    }
                }
                else {
                    k--;
                    while (num[k] == num[k + 1] && j < k) {
                        k--;
                    } 
                }
            }
            
            while (i + 1 <= num.length - 3 && num[i + 1] == num[i]) {
                i++;
            }
        }
        
        return list;
    }
}

Add Two Numbers

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int carry = 0;
        ListNode *root = l1 ? l1 : l2, *node = root;
        while (l1 && l2) {
            int val = l1->val + l2->val + carry;
            if (val > 9) {
                val %= 10;
                carry = 1;
            }
            else {
                carry = 0;
            }
            node = l1;
            node->val = val;
            l1 = l1->next;
            l2 = l2->next;
        }
        
        ListNode *next = l1 ? l1 : l2;
        
        if (next) {
            node->next = next;
            node = node->next;
            
            while (carry != 0) {
                int val = node->val + carry;
                if (val > 9) {
                    node->val = val % 10;
                    carry = 1;
                    if (!node->next) {
                        node->next = new ListNode(1);
                        carry = 0;
                    }
                    else {
                        node = node->next;
                    }
                }
                else {
                    node->val = val;
                    carry = 0;
                }
            }
        }
        
        if (carry != 0) {
            node->next = new ListNode(1);
        }
        
        return root;
    }
};

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

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

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

DP Solution:

public class Solution {
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (prices.length <= 1) return 0;
        int min = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            maxProfit = Math.max(prices[i] - min, maxProfit);
        }
        return maxProfit;
    }
}

Divide-n-Conquer:

public class Solution {
    private class MaxMin {
        public int max;
        public int min;
        public int profit;
        public MaxMin(int max, int min, int profit) {
            this.max = max;
            this.min = min;
            this.profit = profit;
        }
    }
    
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (prices.length <= 1) return 0;
        return _maxProfit(prices, 0, prices.length - 1).profit;
    }
    
    private MaxMin _maxProfit(int[] prices, int left, int right) {
        if (right - left <= 1) {
            MaxMin m = new MaxMin(
                Math.max(prices[right], prices[left]),
                Math.min(prices[right], prices[left]),
                Math.max(0, prices[right] - prices[left]));
            return m;
        }
        int mid = (right + left) / 2;
        MaxMin lm = _maxProfit(prices, left, mid);
        MaxMin rm = _maxProfit(prices, mid+1, right);
        int maxProfit = Math.max(Math.max(lm.profit, rm.profit), rm.max - lm.min);
        int min = Math.min(lm.min, rm.min);
        int max = Math.max(lm.max, rm.max);
        MaxMin m = lm;
        m.min = min;
        m.max = max;
        m.profit = maxProfit;
        return m;
    }
}