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.