Leetcode: Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Solution:

We use binary search to find the place where to insert the element such that all the elements are sorted according to their start times. Then we have to see if we have to merge with the previous one and with all the following ones.

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) 
    {
        int position = findPosition(intervals, newInterval, 0, intervals.size()-1);
        if(position > 0 && intervals.get(position-1).end >= newInterval.start)
        {
            intervals.get(position-1).end = Math.max(intervals.get(position-1).end, newInterval.end);
            position--;
        }
        else
            intervals.add(position, newInterval);
        while (position < intervals.size()-1 && intervals.get(position).end >= intervals.get(position+1).start)
        {
            intervals.get(position).end =   Math.max(intervals.get(position).end, intervals.get(position+1).end);
            intervals.remove(position+1);
        }
        return intervals;
        
    }
    
    private int findPosition(ArrayList<Interval> intervals, Interval target, int start, int end)
    {
        if (end < start)
            return start;
        int midpoint= (start+end) /2;
        if (intervals.get(midpoint).start <= target.start)
            return findPosition(intervals, target, midpoint+1, end);
        return findPosition(intervals, target, start, midpoint-1);
    }
}

Leetcode: Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

Solution:

public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        ArrayList<Integer> solution = new ArrayList<Integer>();
        grayCode(0, n, new boolean[(int)Math.pow(2,n)],solution);
        return solution;
    }
    
    
    
    
    public boolean grayCode(int number, int n, boolean[] used, ArrayList<Integer> solution)
    {
        used[number] = true;
        solution.add(number);
        if (solution.size()== (int) Math.pow(2,n))
            return true;
        for(int i=0; i<n; i++)
        {
           int number2 = number ^ (1<<i);
           if(!used[number2])
           {
                if(grayCode(number2, n, used, solution))
                    return true;
           }
        }
        solution.remove(solution.size()-1);
        used[number]=false;
        return false;
    }
}

Leetcode: Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution:

We use dynamic programming, with the matrix isInterleaved whose element(i,j) indicates if string s3[0,...,i+j-1] can be formed by interleaving s1[0,...,i-1] and s2[0,...,j-1].
Then we can just calculate the element (i,j) by:

isInterleaved[i][j] = (isInterleaved[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1)) || (isInterleaved[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1))
This program could be reduced the space complexity just keeping the previousRow and actualRow, instead of the whole matrix, as done in the Python implementation.

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        boolean[][] isInterleaved = new boolean[s1.length()+1][s2.length()+1];
        if (s3.length() != s1.length()+s2.length())
            return false;
        for(int i=0; i<=s1.length(); i++)
        {
            for(int j=0; j<=s2.length(); j++)
            {
                if(i==0 && j==0)
                {
                    isInterleaved[0][0]=true;        
                    continue;
                }
                boolean value = j>0 ? isInterleaved[i][j-1] && s3.charAt(i+j-1) == s2.charAt(j-1) : false;
                value = i>0 ? value || isInterleaved[i-1][j] && s3.charAt(i+j-1) == s1.charAt(i-1) : value;
                isInterleaved[i][j] = value;
            }
        }
        return isInterleaved[s1.length()][s2.length()];
    }
}

Leetcode: Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

We can use backtracking, only we have to be careful on the definition of ip, for instance 10.01.1.1 is not a valid ip. This means any octet has to be a number from 0 to 255 but if it has more than one digit the first one cannot be a zero.

public class Solution {
    public List<String> restoreIpAddresses(String s) 
    {
        List<String> solution = new ArrayList<String>();
        restoreIpAddresses(s, 0, 0, new StringBuilder(), solution);
        return solution;
    }
    
    public void restoreIpAddresses(String s, int index, int octets, StringBuilder sb, List<String> solution) 
    {
        if(octets==4)
        {
            if(index==s.length())
            {
                sb.deleteCharAt(sb.length()-1);
                solution.add(sb.toString());
                sb.append('.');
            }
            return;
        }
        
        for(int size=1; size<=3; size++)
        {
            if(size>1 && s.charAt(index)=='0')
                break;
            if(s.length()-index-size<3-octets)
                break;
            if(Integer.parseInt(s.substring(index,index+size))>255)
                break;
            sb.append(s.substring(index,index+size));
            sb.append('.');
            restoreIpAddresses(s, index+size, octets+1, sb, solution);
            sb.delete(sb.length()-1-size, sb.length());
        }
    }
}

Leetcode: Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        return sortedArrayToBST(num, 0, num.length-1);
    }
    
    public TreeNode sortedArrayToBST(int[] num, int begin, int end) {
        if (begin>end)
            return null;
        int midPoint= (begin+end)/2;
        TreeNode solution = new TreeNode(num[midPoint]);
        solution.left = sortedArrayToBST(num, begin, midPoint-1);
        solution.right = sortedArrayToBST(num, midPoint+1, end);
        return solution;
    }
}

Leetcode: Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

Solution:

We can use dynamic programming to calculate all the possible substrings if they are palindrome or not and save them in a matrix. Then we use backtracking to generate all the possible partitions.

public class Solution {
    public List<List<String>> partition(String s) {
        boolean [][] isPalindrome = new boolean[s.length()][s.length()];
        for(int length = 0; length < s.length(); length++)
        {
            for(int start = 0; start < s.length()-length; start++)
            {
                if(length==0)
                    isPalindrome[start][start+length] = true;
                else if(length==1)
                    isPalindrome[start][start+length] = s.charAt(start)==s.charAt(start + length);
                else
                    isPalindrome[start][start+length] = isPalindrome[start+1][start+length-1] && s.charAt(start)==s.charAt(start + length);
            }
        }
        
        List<List<String>> solution = new ArrayList<List<String>>();
        partition(s, 0, isPalindrome, new ArrayList<String>(), solution);
        return solution;
    }
    
    private void partition(String s, int index, boolean[][] isPalindrome, ArrayList<String> tempSolution, List<List<String>> solution)
    {
        if(index==s.length())
        {
            solution.add((List<String>) tempSolution.clone());
            return;
        }
        for(int i= index; i<s.length();i++)
        {
            if(isPalindrome[index][i])
            {
                tempSolution.add(s.substring(index,i+1));
                partition(s, i+1, isPalindrome, tempSolution, solution);
                tempSolution.remove(tempSolution.size()-1);
            }
        }
    }
}

Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution:

This problem can be solved recursively if we notice that the last element of the postorder is the root and all the elements that appear before the root in the inorder belong to the left subbranch and the ones that appear after to the right one.

public class Solution {

    public TreeNode buildTree(int[] inorder, int[] postorder) 

    {

        return buildTree(inorder, 0, postorder, 0, inorder.length);

    }

    

    private TreeNode buildTree(int[] inorder, int bi, int[] postorder, int bp, int nelements)

    {

        if(nelements<1)

            return null;

        if (nelements==1)

            return new TreeNode(inorder[bi]);

        TreeNode sol = new TreeNode(postorder[bp+nelements-1]);

        for(int i=0; i<nelements; i++)

        {

            if(inorder[bi+i]==sol.val)

            {

                sol.left=buildTree(inorder, bi, postorder, bp, i);

                sol.right=buildTree(inorder, bi+i+1, postorder, bp+i, nelements-i-1);

                break;

            }

        }

        return sol;

    }

}

Leetcode: Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Divide and Conquer solution

We merge lists by pairs till we have only one list. The complexity is $O(n log(k))$.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size()==0)
            return null;
        while(lists.size()>1)
        {
            List<ListNode> nextLists = new ArrayList<ListNode>();
            for(int i=0; i< lists.size()-1; i+=2)
            {
                nextLists.add(mergeLists(lists.get(i),lists.get(i+1)));
            }
            if (lists.size()%2==1)
                nextLists.add(lists.get(lists.size()-1));
            lists = nextLists;
        }
        return lists.get(0);
    }
    
    private ListNode mergeLists(ListNode list1, ListNode list2)
    {
        ListNode dummy = new ListNode(0);
        ListNode list = dummy;
        while(list1!=null && list2!=null)
        {
            if(list1.val<list2.val)
            {
                list.next = list1;
                list1 = list1.next;
            }
            else
            {
                list.next = list2;
                list2 = list2.next;
            }
            list = list.next;
        }
        if (list1 == null)
            list.next = list2;
        else
            list.next = list1;
        return dummy.next;
    }
}

Leetcode: Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Solution

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    public boolean isValidBST(TreeNode root, int min, int max) 
    {
        if(root == null)
            return true;
        if(root.val>=max || root.val<=min)
            return false;
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

Leetcode: Subsets

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution:

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        List<List<Integer>>solution = new ArrayList<List<Integer>>();
        subsets(S, 0,new ArrayList<Integer>(), solution);
        return solution;
    }
    
    private void subsets(int[] S, int index, ArrayList<Integer> tempSolution, List<List<Integer>>solution)
    {
        if (index==S.length)
        {
            solution.add((List<Integer>)tempSolution.clone());
            return;
        }
            
        // Not adding the element
        subsets(S, index+1, tempSolution, solution);
        
        tempSolution.add(S[index]);
        subsets(S, index+1, tempSolution, solution);
        tempSolution.remove(tempSolution.size()-1);
    }
}

Leetcode: Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution:

public class Solution {
    public int longestValidParentheses(String s) {
        ArrayDeque<Integer> positions = new ArrayDeque<Integer>();
        int lastError = -1;
        int longestChain = 0;
        for(int i=0; i<s.length(); i++)
        {
            if(s.charAt(i)=='(')
                positions.push(i);
            else
            {
                if(positions.isEmpty())
                    lastError = i;
                else
                {
                    positions.pop();
                    int previousValue = positions.isEmpty() ? lastError : positions.peek();
                    longestChain = longestChain < i-previousValue ? i-previousValue : longestChain;
                }
            }
        }
        return longestChain;
    }
}

LeetCode: Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution:

public class Solution {
    public int[][] generateMatrix(int n) {
        int sol[][] = new int[n][n];
        int count = 0;
        int row = 0;
        int col = 0;
        int direction = 1; //1 to the right,  2 to the bottom, 3 to the lift, 4 to the top
        while ( count< n*n)
        {
            sol[row][col] = ++count;
            switch(direction)
            {
                case 1:
                    col++;
                    if( col >= n-1 || sol[row][col+1] != 0) 
                        direction = 2;
                    break;
                case 2:
                    row++;
                    if( row >= n-1 || sol[row+1][col] != 0) 
                        direction = 3;
                    break;
                case 3:
                    col--;
                    if( col <= 0 || sol[row][col-1] != 0) 
                        direction = 4;
                    break;
                case 4: row--;
                    if( row <= 0 || sol[row-1][col] != 0) 
                        direction = 1;
                    break;
            }
        }
        return sol;
    }
}

Leetcode: Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution:

public class Solution {

    public ArrayList<ArrayList<Integer>> combine(int n, int k) {

        ArrayList<ArrayList<Integer>> solution = new ArrayList<ArrayList<Integer>>();

        combine(1, n, k, new int[k],  solution);

        return solution;

    }

    

    public void combine(int start, int end, int numbersLeft, int[] partial, ArrayList<ArrayList<Integer>> solution) 

    {

        if (numbersLeft==0)

        {

            ArrayList<Integer> temp = new ArrayList<Integer>();

            for(int k=0; k<partial.length; k++) temp.add(partial[k]); 

            solution.add(temp);

            return;

        }

        

        for(int i=start; i<=end-numbersLeft+1; i++)

        {

            partial[partial.length-numbersLeft] = i;

            combine(i+1, end, numbersLeft-1, partial,  solution);    

        }

    }

}

LeetCode: Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Solution:

public class Solution {
    public int minPathSum(int[][] grid) {
        if(grid.length == 0 || grid[0].length==0)
            return 0;
        for(int row = 0; row<grid.length; row++)
        {
            for(int col=0; col<grid[0].length; col++)
            {
                if (col>0 && row>0)
                    grid[row][col] += Math.min(grid[row][col-1], grid[row-1][col]);
                else if (col>0)
                    grid[row][col] += grid[row][col-1];
                else if (row>0)
                    grid[row][col] += grid[row-1][col];
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}

LeetCode: Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> solution = new ArrayList<List<Integer>>();
        ArrayList<TreeNode> thisLevel = new ArrayList<TreeNode>();
        if (root!=null)
            thisLevel.add(root);
        while(thisLevel.size()>0)
        {
            ArrayList<Integer> thisLevelNumbers = new ArrayList<Integer>();
            ArrayList<TreeNode> nextLevel = new ArrayList<TreeNode>();
            for(TreeNode tempNode: thisLevel)
            {
                thisLevelNumbers.add(tempNode.val);
                if (tempNode.left != null)
                    nextLevel.add(tempNode.left);
                if (tempNode.right != null)
                    nextLevel.add(tempNode.right);
            }
            solution.add(0, thisLevelNumbers);
            thisLevel = nextLevel;
        }
        return solution;
    }
}

Leetcode: Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

Solution:

The result can be seen as $a_n 2^n+ a_{n-1} 2^{n-1}+\dots+a_1 *2 +a_0$, with $a_i \in \{0,1\}$. Our solution calculates first n by obtaining the largest n that $\text{divisor} \cdot 2^n \leq \text{dividend}$. Then we just have to calculate $a_i = \left( \text{dividend} - \sum_{j=i+1}^n a_j \text{divisor} \cdot 2^j\right)>= 2^i$, even the expression is complex the code is much simpler:
We had to change integers into longs to avoid the overflowing problem of -Integer.MIN_VALUE cannot be contained in an int.

public class Solution {
    public int divide(int dividend, int divisor) {
        long dividendL = dividend<0 ?-(long)dividend : (long)dividend;
        long divisorL = divisor<0 ? -(long)divisor : (long)divisor;
        if(dividendL<divisorL) return 0;
        long temp =divisorL;
        long result=0;
        long i=1;

        //We calculate n and 2^n
        while((temp<<1)<=dividendL)
        {
            temp<<=1;
            i<<=1;
        }
        
        //We calculate a_i and acumulate them in result
        while (dividendL>0 && i>0)
        {
            if(temp<=dividendL)
            {
                dividendL-=temp;
                result +=i;
            }
            temp>>=1;
            i>>=1;
        }
        return ((dividend & 0x80000000)^(divisor & 0x80000000)) ==0 ? (int)result : (int)(-result);
    }
}

Leetcode: Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Solution: Extra space O(n)

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> solution = new ArrayList<ArrayList<Integer>> ();
        HashSet<Integer> used = new HashSet<Integer>();
        ArrayList<Integer> oneSolution = new ArrayList<Integer>();
        permute(num, used, solution, oneSolution);
        return solution;
    }
    private void permute(int[] num, HashSet<Integer> used, ArrayList<ArrayList<Integer>> solution, ArrayList<Integer> oneSolution) 
    {
        if(oneSolution.size()==num.length)
        {
            solution.add(oneSolution);
            return;
        }
        for(int i=0; i< num.length; i++)
        {
            if(!used.contains(num[i]))
            {
                used.add(num[i]);
                ArrayList<Integer> tempSolution = (ArrayList<Integer>) oneSolution.clone();
                tempSolution.add(num[i]);
                permute(num, used, solution, tempSolution);
                used.remove(num[i]);
            }
        }
    }
}

Solution 2: Swap based (No additional data structures)

public class Solution {

    public ArrayList<ArrayList<Integer>> permute(int[] num) {

        ArrayList<ArrayList<Integer>> solution = new ArrayList<ArrayList<Integer>> ();

        permute(num, 0, solution);

        return solution;

    }

   

    private void permute(int[] num, int index, ArrayList<ArrayList<Integer>> solution) 

    {

        if(index+1==num.length)

        {

            ArrayList<Integer> sol= new ArrayList<Integer>();

            for (int i=0; i<num.length; i++)

                sol.add(num[i]);

            solution.add(sol);

            return;

        }

        permute(num, index+1, solution);

        for(int i=index+1; i<num.length; i++)

        {

            swap(num, index,i);

            permute(num, index+1, solution);

            swap(num, i, index);

        }

    }

    

    private void swap(int[] num, int i, int j)

    {

        int temp = num[i];

        num[i] = num[j];

        num[j] = temp;

    }

}

Leetcode: Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Solution:

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode firstNodeLevel = root;
        TreeLinkNode firstNodeNextLevel = null;
        while(firstNodeLevel != null)
        {
            TreeLinkNode pointer = firstNodeLevel;
            TreeLinkNode nextLevelTemp = null;
            while(pointer!=null)
            {
                if(pointer.left!=null)
                {
                    if(firstNodeNextLevel == null)
                        firstNodeNextLevel = pointer.left;
                    else
                        nextLevelTemp.next = pointer.left;
                    nextLevelTemp = pointer.left;
                }
                if(pointer.right!=null)
                {
                    if(firstNodeNextLevel == null)
                        firstNodeNextLevel = pointer.right;
                    else
                        nextLevelTemp.next = pointer.right;
                    nextLevelTemp = pointer.right;
                }
                pointer = pointer.next;
            }
            firstNodeLevel = firstNodeNextLevel;
            firstNodeNextLevel = null;
        }
        
    }
}

Leetcode: Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution:

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        return cloneGraph(node, new HashMap<Integer,UndirectedGraphNode>());
    }
    
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node, HashMap<Integer,UndirectedGraphNode> map) 
    {
        if(node == null)
            return null;
        if (map.containsKey(node.label))
            return map.get(node.label);
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        map.put(node.label, newNode);
        for(UndirectedGraphNode neighbor: node.neighbors)
            newNode.neighbors.add(cloneGraph(neighbor, map));
        return newNode;
    }
}

Leetcode: Add Binary

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

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

Solution:

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder solution = new StringBuilder();
        int sum = 0;
        for(int i = 0; i < Math.max(a.length(), b.length()); i++)   
        {
            sum += i<a.length() && a.charAt(a.length()-1-i) == '1' ? 1 : 0;
            sum += i<b.length() && b.charAt(b.length()-1-i) == '1' ? 1 : 0;
            solution.insert(0, sum% 2);
            sum /= 2;
        }
        if (sum >0)
            solution.insert(0, sum% 2);
        return solution.toString();
    }
}

Leetcode: Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Solution:

 public class Solution {
    public ArrayList<String> fullJustify(String[] words, int L) {
        int wordStartLine = 0;
        int charactersInThisLine = 0;
        int wordsInThisLine = 0;
        ArrayList<String> solution = new ArrayList<String>();
        StringBuilder line = new StringBuilder();
        for(int i=0; i<words.length; i++)
        {
            if(charactersInThisLine+wordsInThisLine+words[i].length()>L)
            {
                line = new StringBuilder();
                int numSpaces = 0;
                int extraSpaces=0;
                if(wordsInThisLine>1)
                {
                    numSpaces= (L-charactersInThisLine)/(wordsInThisLine-1);
                    extraSpaces = (L-charactersInThisLine)%(wordsInThisLine-1);
                }
                for(int j=wordStartLine; j<i; j++)
                {
                    line.append(words[j]);
                    if(j==i-1)
                        break;
                    for(int n=0; n<numSpaces; n++)
                        line.append(' ');
                    if(j-wordStartLine<extraSpaces)
                        line.append(' ');
                }
                for(int j=line.length(); j<L;j++)
                    line.append(' ');
                solution.add(line.toString());
                wordStartLine = i;
                charactersInThisLine = 0;
                wordsInThisLine = 0;
            }
            charactersInThisLine += words[i].length();
            wordsInThisLine ++;
        }
        
        if(solution.size()==0 || wordStartLine<words.length)
        {
            line = new StringBuilder();
            for(int j=wordStartLine; j<words.length; j++)
            {
                line.append(words[j]);
                if(j==words.length-1)
                    break;
                line.append(' ');
            }
            for(int j=line.length(); j<L;j++)
                line.append(' ');
            solution.add(line.toString());
        }
        
        return solution;
    }
}

Leetcode: Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution 1 O($\log(m+n)$):

Note that we can check if an element A[i] is the median in constant time. Since the array is sorted A[i] is larger than i elements from array A, then if it is the median it needs to be larger than $\lfloor \frac{m+n}{2} \rfloor -i$ elements in array B. Hence to be the median i would mean that $B[j]\leq A[i]\leq B[j+1]$, where j=(m+n)/2-i-1. If it is not the median we can also know if A[i] is larger than the median, i.e. A[i]>B[j+1]. or smaller, i.e. A[i]<B[j]. Note that in the case of $m+n$ being even we have to obtain the previous element and return the average.

public class Solution {

  public double findMedianSortedArrays(int A[], int B[]) 

  {

     //Empty array cases

       if((A ==null || A.length==0) &&(B==null || B.length==0)) return 0.0;

     if(A==null || A.length==0) return B.length%2==1 ? B[B.length/2] :  (B[B.length/2]+B[B.length/2-1])/2.0;

     if(B==null || B.length==0) return A.length%2==1 ? A[A.length/2] :  (A[A.length/2]+A[A.length/2-1])/2.0;

     if(A.length>B.length) return findMedianSortedArrays(A, B, 0, A.length-1);

return findMedianSortedArrays(B, A, 0, B.length-1);

  }

  private double findMedianSortedArrays(int[] A, int[] B, int begin, int end) 

  {

if(begin>end) return findMedianSortedArrays(B, A, 0, B.length-1);

int i = (begin+end)/2;

int j = (A.length+B.length)/2-i-1;

if(j>=B.length || j>=0 && B[j]>A[i]) return findMedianSortedArrays(A, B, i+1, end); //A[i]>median

else if(j<-1 || j<B.length-1 && B[j+1]<A[i]) return findMedianSortedArrays(A, B, begin, i-1); //A[i]<median

if ((A.length+B.length)%2==1) //It is the median or the last element of the two that are needed

return A[i];

if(j>=0 && ( i==0 || B[j]>A[i-1]))

return (B[j]+A[i])/2.0;

return (A[i-1]+A[i])/2.0;

   }

}

Algorithm based on the idea given in [1]

Solution 2 O($\log^2(m+n)$):

Let's base our algorithm in binary search. If we select a candidate to be the median and we find the number of elements smaller than this element in the other array, we can shrink the arrays correspondingly.

public class Solution {
  public double findMedianSortedArrays(int A[], int B[]) 
  {
     if((A ==null || A.length==0) &&(B==null || B.length==0)) return 0.0;
     if(A==null || A.length==0) return B.length%2==1 ? B[B.length/2] :  (B[B.length/2]+B[B.length/2-1])/2.0;
     if(B==null || B.length==0) return A.length%2==1 ? A[A.length/2] :  (A[A.length/2]+A[A.length/2-1])/2.0;

     if(A.length>B.length)
return findMedianSortedArrays(A, B, 0, A.length-1, 0,B.length-1);
     return findMedianSortedArrays(B, A, 0, B.length-1, 0,A.length-1);
  }

  private double findMedianSortedArrays(int[] A, int[] B, int beginA, int endA, int beginB, int endB) 
  {
int pivot = A[(beginA+endA)/2];
int pos = binarySearch(B,beginB,endB+1,pivot);
int smallerThanPivot = (beginA+endA)/2 +pos;
if(smallerThanPivot<(A.length+B.length-1)/2)
{
   beginA=(beginA+endA)/2+1;
   beginB=pos;
      if(endA-beginA>endB-beginB) 
                return findMedianSortedArrays(A, B, beginA, endA, beginB,endB);
   else 
                return findMedianSortedArrays(B, A, beginB, endB, beginA,endA);
}
if(smallerThanPivot>(A.length+B.length-1)/2)
{
   endA=(beginA+endA)/2-1;
   endB=pos-1;
   if(endA-beginA>endB-beginB)
                return findMedianSortedArrays(A, B, beginA, endA, beginB,endB);
   else 
                return findMedianSortedArrays(B, A, beginB, endB, beginA,endA);
}
if ((A.length+B.length)%2==1)
    return pivot;
int next = (beginA+endA)/2+1<A.length ? A[(beginA+endA)/2+1] : Integer.MAX_VALUE;
next = pos<B.length && B[pos]<next ? B[pos] : next;
return (pivot+next)/2.0;
   }

   private int binarySearch(int[] A, int begin, int end, int value)
   {
        //We assure that A[0..begin-1]<=value<=A[end+1...]
if(begin>=end)
   return begin;
int midpoint=(begin+end)/2;
if (A[midpoint]==value) return midpoint;
else if (A[midpoint]<value) return binarySearch(A, midpoint+1, end, value);
else return binarySearch(A, begin, midpoint, value);
   }
}

[1] E. D. Demaine, C. E. Leiserson, "Introduction to Algorithms. Problem Set 9 Solutions " Available at: http://www2.myoops.org/course_material/mit/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf