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;

    }

}