Leetcode: Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution:

/**
 * 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 List<Interval> merge(List<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        });
        int i=1;
        while(i<intervals.size())
        {
            if (intervals.get(i-1).end >= intervals.get(i).start)
            {
                intervals.get(i-1).end = Math.max(intervals.get(i-1).end, intervals.get(i).end);
                intervals.remove(i);
            }
            else
                i++;
        }
        return intervals;
    }
    
}

Leetcode: Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

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

Solution:

We count the number of elements an element appears in a hashmap (we used a LinkedHashMap to guarantee that the order of iteration is always the same). Then we use a recursive solution where we iterate through the different elements of the collection and keeping the number of times an element has been used in an array.

import java.util.LinkedHashMap;

public class Solution {

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) 

    {

        LinkedHashMap<Integer, Integer> numberofElements = new LinkedHashMap<Integer, Integer>();

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

        {

            if(!numberofElements.containsKey(num[i]))

                numberofElements.put(num[i],1);

            else

                numberofElements.put(num[i],numberofElements.get(num[i])+1);

        }

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

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

        permuteUnique(num, sol, permutation, numberofElements, new int[numberofElements.size()]);

        return sol;

    }

    

    public void permuteUnique(int[] num, ArrayList<ArrayList<Integer>> sol, ArrayList<Integer> permutation, LinkedHashMap<Integer, Integer>numberofElements, int[] used) 

    {

        if(permutation.size()==num.length)

        {

            sol.add((ArrayList<Integer>)permutation.clone());

            return;

        }

        int i=0;

        for(Integer val: numberofElements.keySet())

        {

            if(used[i]<numberofElements.get(val))

            {

                used[i]++;

                permutation.add(val);

                permuteUnique(num, sol, permutation, numberofElements, used);

                permutation.remove(permutation.size()-1);

                used[i]--;

            }

            i++;

        }

    }

}

Leetcode: Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Solution

If we traverse the tree inorder, we just need to identify the 2 elements that are misplaced and swap their values. We also keep a third pointer that points to the previous element as it is needed to identify when an element is misplaced.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode pre, node1, node2;   
    public void recoverTree(TreeNode root) {
        pre =null;
        node1 = null;
        node2 = null;
        inOrder(root);
        int temp = node1.val;
        node1.val = node2.val;
        node2.val = temp;
    }
    
    private void inOrder(TreeNode root)
    {
        if (root == null)
            return;
        inOrder(root.left);
        if(pre == null)
            pre = root;
        else if(node1 == null && pre.val > root.val)
        {
            node1 = pre;
            node2 = root;
        }
        else if(pre.val > root.val)
        {
            node2 = root;
        }
        pre = root;
        inOrder(root.right);
    }
}

Leetcode: Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8, 
A solution set is: 
[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

Solution

public class Solution {
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        List<List<Integer>> solution = new ArrayList<List<Integer>>();
        Arrays.sort(num);
        combinationSum2(num, target, 0, 0, new ArrayList<Integer>(), solution);
        return solution;
    }
    
    public void combinationSum2(int[] num, int target, int index, int currentSum, ArrayList<Integer> current,  List<List<Integer>> solution)
    {
        if(currentSum == target)
        {
            solution.add((ArrayList<Integer>)current.clone());
            return;
        }
        for(int i=index; i< num.length; i++)
        {
            if((i==index || num[i-1]<num[i]) && currentSum+num[i]<=target)
            {
                current.add(num[i]);
                combinationSum2(num, target, i+1, currentSum+num[i], current,  solution);
                current.remove(current.size()-1);
            }
        }
        
    }
}

Leetcode: Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Solution

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] solution = {-1,-1};
        int start = 0;
        int end = A.length-1;
        while(start<end)
        {
            int midpoint = (start+end)/2;
            if (A[midpoint]==target)
                end = midpoint;
            else if (A[midpoint]<target)
                start = midpoint+1;
            else
                end = midpoint-1;
        }
        if (A[start] !=target)
            return solution;
        else
            solution[0]=start;
        end = A.length -1;
        while(start<end)
        {
            int midpoint = (start+end+1)/2;
            if (A[midpoint]==target)
                start = midpoint;
            else
                end = midpoint-1;
        }
        solution[1]= start;
        return solution;
    }
}

Leetcode: First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution:

We could use a boolean array of length n in order to indicate whether the element is present or not, but instead of creating this array we are going to use the input array to mark it we use the sign for this. Hence we have to remove all the negative or zero values before. 

public class Solution {

    public int firstMissingPositive(int[] A) {

        int length = A.length;

        int i=0;

        while(i<length)

        {

            if(A[i]<=0)

                swap(A,i,--length);

            else

                i++;

        }

        for(i=0; i<length; i++)

        {

            if(Math.abs(A[i])<=length)

                A[Math.abs(A[i])-1]=-Math.abs(A[Math.abs(A[i])-1]);

        }

        for(i=0; i<length; i++)

        {

            if(A[i]>0)

                return i+1;

        }

        return length+1;

    }

    

    private void swap(int[] A, int pos1, int pos2)

    {

        int temp=A[pos1];

        A[pos1]=A[pos2];

        A[pos2]=temp;

    }

}

Leetcode: Best Time to Buy and Sell Stock III

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

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 

Solution

We can calculate the solution to the problem for 1 transaction, so we use dynamic programming calculating the solution to which is the maximum benefit prior and posterior to certain day, afterwards we just have to iterate through the sum of both arrays finding the maximum.

public class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int previousMin = Integer.MAX_VALUE;
        int nextMax = Integer.MIN_VALUE;
        int[] maxProfitSellBefore = new int[prices.length];
        int[] maxProfitBuyAfter = new int[prices.length];
        for(int i=0; i<prices.length;i++)
        {
            previousMin = Math.min(previousMin,prices[i]);
            maxProfitSellBefore[i] = i>0 ? Math.max(maxProfitSellBefore[i-1], prices[i]-previousMin) : 0;
        }
        for(int i=prices.length-1; i>=0;i--)
        {
            nextMax = Math.max(nextMax,prices[i]);
            maxProfitBuyAfter[i] = i<prices.length-1 ? Math.max(maxProfitBuyAfter[i+1], nextMax-prices[i]) : 0;
        }
        for(int i=0; i<prices.length;i++)
        {
            maxProfit = Math.max(maxProfit, maxProfitSellBefore[i]+maxProfitBuyAfter[i]);
        }
        return maxProfit;
    }
}

Leetcode: Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

Solution:

We implement it as a state-machine with two states

where in the transition we add the word or mark the beginning.

public class Solution {
    public String reverseWords(String s) {
        StringBuilder solution = new StringBuilder();
        int startOfWord = 0;
        boolean inWord = false;
        for(int i=0; i<s.length(); i++)
        {
            if(s.charAt(i)==' ' || s.charAt(i)=='\t')
            {
                if (inWord)
                {
                    solution.insert(0,s.substring(startOfWord,i));
                    solution.insert(0,' ');
                    inWord = false;
                }
            }
            else
            {
                if (!inWord)
                {
                    inWord=true;
                    startOfWord = i;
                }
            }
        }
        if (inWord)
        {
            solution.insert(0,s.substring(startOfWord,s.length()));
            solution.insert(0,' ');
        }
        if (solution.length()>0)
            solution.deleteCharAt(0);
        return solution.toString();
    }
}

Leetcode: Multiply Strings

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Solution:

We precalculate num1 multiplied by [0...9] and keep the result afterwards we just follow the algorithm typical of multiplying in paper, i.e. 123*456 = 123*6+ 123*5 *10 + 123*4*100, where the last multiplication is just adding zeros.

public class Solution {
    public String multiply(String num1, String num2) 
    {
        StringBuilder result=new StringBuilder();
        int carryOn=0;
        for(int i=num2.length()-1; i>=0; i--)
        {
              StringBuilder tempResult=new StringBuilder();
              for(int j=num1.length()-1; j>=0; j--)
              {
                carryOn += (Character.getNumericValue(num1.charAt(j)) * Character.getNumericValue(num2.charAt(i)));
                tempResult.insert(0,carryOn%10);
                carryOn /= 10;
              }
              if(carryOn>0)
              {
                tempResult.insert(0,carryOn%10);
                carryOn =0;
              }
              for(int j=i; j<num2.length()-1; j++)
                tempResult.append('0');
              result = sum(result,tempResult);
        }
        removeZeros(result);
        return result.toString();
    }
    
    public StringBuilder sum(StringBuilder sum1, StringBuilder sum2)
    {
        int carryOn = 0;
        StringBuilder result = new StringBuilder();
        for(int i=0; i<sum2.length() || i<sum1.length(); i++)
        {
            if(i<sum2.length())
                carryOn += Character.getNumericValue(sum2.charAt(sum2.length()-1-i));
            if(i<sum1.length())
                carryOn += Character.getNumericValue(sum1.charAt(sum1.length()-1-i));
            result.insert(0,carryOn%10);
            carryOn /= 10;
        }
        if(carryOn>0)
                result.insert(0,carryOn%10);
        return result;
    }
    
    public void removeZeros(StringBuilder num)
    {
        while(num.length()>1 &&num.charAt(0)=='0')
            num.deleteCharAt(0);
    }
}

Leetcode: Subsets II

Given a collection of integers that might contain duplicates, 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,2], a solution is:

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

Solution:

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> solution = new ArrayList<List<Integer>>();
        subsetsWithDup(num, 0, new ArrayList<Integer>(), solution);
        return solution;
    }
    
    public void subsetsWithDup(int[] num, int index, ArrayList<Integer> tempSolution, List<List<Integer>> solution) {
        if(index == num.length)
        {
            solution.add((List<Integer>)tempSolution.clone());
            return;
        }
        
        //Do not add element num[i]
        int value = num[index];
        int i= index;
        while(i<num.length && num[i]==value)
            i++;
        subsetsWithDup(num, i, tempSolution, solution);
            
        //Add element num[i]
        tempSolution.add(num[index]);
        subsetsWithDup(num, index+1, tempSolution, solution);
        tempSolution.remove(tempSolution.size()-1);
    }
}

Leetcode: Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

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

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

Solution

We use a variant of BFS with two stacks, one for this level one for the next one. As we traverse one level we add the children into the next level stack, once a level is traversed the next level stack becomes the actual one.

/**
 * 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>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> solution = new ArrayList<List<Integer>>();
        ArrayDeque<TreeNode> thisLevel = new ArrayDeque<TreeNode>();
        boolean leftToRight = true;
        if(root != null)
            thisLevel.add(root);
        while(!thisLevel.isEmpty())
        {
            List<Integer> level = new ArrayList<Integer>();
            ArrayDeque<TreeNode> nextLevel = new ArrayDeque<TreeNode>();
            while(!thisLevel.isEmpty())
            {
                TreeNode temp = thisLevel.pop();
                level.add(temp.val);
                if(leftToRight)
                {
                    if(temp.left != null)
                        nextLevel.push(temp.left);
                    if(temp.right != null)
                        nextLevel.push(temp.right);
                }
                else
                {
                    if(temp.right != null)
                        nextLevel.push(temp.right);
                    if(temp.left != null)
                        nextLevel.push(temp.left);
                }
            }
            leftToRight = !leftToRight;
            thisLevel = nextLevel;
            solution.add(level);
        }
        return solution;
    }
}

Leetcode: Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Solution:

public class Solution {

    public ListNode reverseBetween(ListNode head, int m, int n) {

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode list1, listReversedStart, listReversedEnd;

        list1=dummy;

        for(int i=1; i<m;i++)

        {

            list1=head;

            head=head.next;

        }

        listReversedEnd=head;

        listReversedStart=head;

        for(int i=0; i<=(n-m);i++)

        {

            ListNode temp = head;

            head=head.next;

            temp.next = listReversedStart;

            listReversedStart = temp;

        }

        list1.next=listReversedStart;

        listReversedEnd.next = head;

        return dummy.next;

    }

}