Given n non-negative integers a₁, a₂, …, a_n , where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7] 
Output: 49

class Solution {
    public int maxArea(int[] height) {
        
    }
}

Idea - 1

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        
        for(int i = 0; i < height.length-1; ++i)
        {
            for(int j = i+1; j < height.length; ++j)
            {
                int curr = Math.min(height[i], height[j])*(j-i);
                max = Math.max(curr, max);
            }
        }
        
        return max;
    }
}


Runtime: 206 ms, faster than 20.38% of Java online submissions for Container With Most Water.
Memory Usage: 41.3 MB, less than 5.05% of Java online submissions for Container With Most Water.

Idea - 2

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length-1;
        int max = 0;
        
        while(i < j)
        {
            int w = j-i;
            int h = Math.min(height[i], height[j]);
            
            max = Math.max(max, w*h);
            
            if(height[i] == h)
            {
                ++i;
            }
            else
            {
                --j;
            }
        }
        
        return max;
    }
}


Runtime: 2 ms, faster than 97.80% of Java online submissions for Container With Most Water.
Memory Usage: 40.6 MB, less than 22.88% of Java online submissions for Container With Most Water.

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example: 

You may serialize the following tree:     
                                          1    
                                         / \   
                                        2   3      
                                           / \     
                                          4   5 
as "[1,2,3,null,null,4,5]" 

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Idea - 1

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        
        if(root==null)
        {
            return "null";
        }
        
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> q = new ArrayDeque<>();
        q.addLast(root);
        
        sb.append(String.format("%s,", root.val));
        
        while(!q.isEmpty())
        {
            TreeNode front = q.removeFirst();
            String leftString = front.left==null ? "null" : String.valueOf(front.left.val);
            sb.append(String.format("%s,", leftString));
            
            if(front.left != null)
            {
                q.addLast(front.left);
            }
            
            String rightString = front.right==null ? "null" : String.valueOf(front.right.val);
            sb.append(String.format("%s,", rightString));
            
            if(front.right != null)
            {
                q.addLast(front.right);
            }
        }
        
        String result = sb.toString();
        
        // skip trailing comma
        return result.substring(0, result.length()-1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("null"))
        {
            return null;
        }
        
        String[] nodes = data.split(",");
        int i = 0;
        TreeNode root = new TreeNode(Integer.parseInt(nodes[i++]));
        List<TreeNode> previousLevel = new ArrayList<>();
        previousLevel.add(root);
        
        while(!previousLevel.isEmpty())
        {
            List<TreeNode> currentLevel = new ArrayList<>();
            for(TreeNode p : previousLevel)
            {
                String leftString = nodes[i++];
                if(!leftString.equals("null"))
                {
                    TreeNode leftChild = new TreeNode(Integer.parseInt(leftString));
                    p.left = leftChild;
                    
                    currentLevel.add(leftChild);
                }
                
                String rightString = nodes[i++];
                if(!rightString.equals("null"))
                {
                    TreeNode rightChild = new TreeNode(Integer.parseInt(rightString));
                    p.right = rightChild;
                    
                    currentLevel.add(rightChild);
                }
            }
            
            previousLevel = currentLevel;
        }
        
        return root;
    }
}


Runtime: 53 ms, faster than 17.30% of Java online submissions for Serialize and Deserialize Binary Tree.
Memory Usage: 46.8 MB, less than 5.05% of Java online submissions for Serialize and Deserialize Binary Tree.

Idea - 2

    public String serialize(TreeNode root) {
        
        if(root==null)
        {
            return "null";
        }
        
        StringBuilder sb = new StringBuilder();
        
        traversePreorder(root, sb);
        
        String result = sb.toString();
        
        return result.substring(0, result.length()-1);
    }
    
    private void traversePreorder(TreeNode x, StringBuilder sb)
    {
        if(x==null)
        {
            sb.append(String.format("null,"));
            return;
        }
        
        sb.append(String.format("%s,", x.val));
        traversePreorder(x.left, sb);
        traversePreorder(x.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("null"))
        {
            return null;
        }
        
        String[] nodeStrings = data.split(",");
        int[] I = {0};
        return buildFromPreorder(nodeStrings, I);
    }
    
    private TreeNode buildFromPreorder(String[] nodeStrings, int[] I)
    {
        int i = I[0];
        if(i >= nodeStrings.length || nodeStrings[i].equals("null"))
        {
            return null;
        }
        
        TreeNode x = new TreeNode( Integer.parseInt(nodeStrings[i]) );
        ++I[0];
        x.left = buildFromPreorder(nodeStrings, I);
        ++I[0];
        x.right = buildFromPreorder(nodeStrings, I);
        
        return x;
    }
}


Runtime: 44 ms, faster than 18.75% of Java online submissions for Serialize and Deserialize Binary Tree.
Memory Usage: 40.7 MB, less than 41.81% of Java online submissions for Serialize and Deserialize Binary Tree.

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4] 
Output: [24,12,8,6] 

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        
    }
}

Idea - 1

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        if(n<2)
        {
            return nums;
        }
        
        int[] l2r = new int[n];
        l2r[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            l2r[i] = l2r[i-1]*nums[i];
        }
        
        int[] r2l = new int[n];
        r2l[n-1] = nums[n-1];
        for(int i = n-2; i >= 0; --i)
        {
            r2l[i] = nums[i]*r2l[i+1];
        }
        
        int[] result = new int[n];
        for(int i = 0; i < n; ++i)
        {
            int left = (i-1 >= 0) ? l2r[i-1] : 1;
            int right = (i+1 < n) ? r2l[i+1] : 1;
            
            result[i] = left*right;
        }
        
        return result;
    }
}


Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.
Memory Usage: 42.6 MB, less than 69.83% of Java online submissions for Product of Array Except Self.

Idea - 2

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        if(n<2)
        {
            return nums;
        }
        
        int[] result = new int[n];
        result[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            result[i] = result[i-1]*nums[i];
        }
        
        int right = 1;
        for(int i = n-1; i >= 0; --i)
        {
            int left = (i-1) >= 0 ? result[i-1] : 1;
            result[i] = left*right;
            right *= nums[i];
        }
        
        return result;
    }
}


Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self.
Memory Usage: 42.2 MB, less than 70.06% of Java online submissions for Product of Array Except Self.

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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4] 
Output: 5 
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price. 

Example 2:

Input: [7,6,4,3,1] 
Output: 0 
Explanation: In this case, no transaction is done, i.e. max profit = 0.

class Solution {
    public int maxProfit(int[] prices) {
        
    }
}

Idea - 1

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2)
        {
            return 0;
        }
        
        int maxprofit = 0;
        for(int i = 0; i < n-1; ++i)
        {
            for(int j = i+1; j < n; ++j)
            {
                maxprofit = Math.max(maxprofit, prices[j]-prices[i]);
            }
        }
        
        return maxprofit;
    }
}


Runtime: 175 ms, faster than 7.70% of Java online submissions for Best Time to Buy and Sell Stock.
Memory Usage: 39.6 MB, less than 28.63% of Java online submissions for Best Time to Buy and Sell Stock.

Idea - 2

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n < 2)
        {
            return 0;
        }
        
        int maxprofit = 0;
        int minsofar = prices[0];
        for(int i = 1; i < n; ++i)
        {
            maxprofit = Math.max(maxprofit, prices[i]-minsofar);
            minsofar = Math.min(minsofar, prices[i]);
        }
        
        return maxprofit;
    }
}


Runtime: 1 ms, faster than 81.15% of Java online submissions for Best Time to Buy and Sell Stock.
Memory Usage: 38.7 MB, less than 53.71% of Java online submissions for Best Time to Buy and Sell Stock.