Leetcode: Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Solution:

Using dynamic programming, we keep in the ith element of an array all the posible sentences from the ith letter.

public class Solution {

    public ArrayList<String> wordBreak(String s, Set<String> dict) {

        ArrayList words[] = new ArrayList [s.length()];

        for(int i=s.length-1; i>=0; i--)

        {

            words[i] = new ArrayList<String>();

            for(int j=i+1; j<=s.length(); j++)

            {

                if(dict.contains(s.substring(i,j)))

                {

                    if(j==s.length())

                    {

                        words[i].add(s.substring(i,j));

                    }

                    else 

                    {

                        for(int k=0; k<words[j].size(); k++)

                            words[i].add(s.substring(i,j)+" "+words[j].get(k));

                    }

                }

            }

        }

        return (ArrayList<String>) words[0];

    }

}

Leetcode: Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Solution:

We first create a map of the points and the number of appearances. Then we traverse the array in a double loop to create all the possible lines keeping them in a HashMap, thus we have to override the equals and hashCode. We also keep the points in each Line instance.
The whole algorithm runs in $O(n^2)$.

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) 
    {
        int nPoints = 0;
        //Remove duplicates
        HashMap<Point, Integer> pointMap = new HashMap<Point, Integer>();
        for(int i=0; i<points.length; i++)
        {
            if(!pointMap.containsKey(points[i]))
                pointMap.put(points[i],0);
            pointMap.put(points[i],pointMap.get(points[i])+1);
        }
        HashMap<Line, Line> lines = new HashMap<Line, Line>();
        Point[] points2 = pointMap.keySet().toArray(new Point[0]);
        for(int i=0; i<points2.length-1; i++)
        {
            for(int j=i+1; j<points2.length; j++)
            {
                Line l = new Line(points2[i],points2[j],pointMap.get(points2[i]),pointMap.get(points2[j]));
                if(!lines.containsKey(l))
                    lines.put(l,l);
                else
                {
                    lines.get(l).addPoint(points2[i], pointMap.get(points2[i]));
                    lines.get(l).addPoint(points2[j], pointMap.get(points2[j]));
                }
                nPoints = lines.get(l).getNumberPoints() > nPoints ? lines.get(l).getNumberPoints() : nPoints;
            }
        }
        return nPoints>0 ? nPoints : points.length;
    }
    
    public class Line
    {
        double yo;
        double slope;
        int nPoints=0;
        HashSet<Point> pointsLine;
        
        public Line(Point p1, Point p2, int p1Apearances, int p2Apearances)
        {
            if(p2.x == p1.x)
            {
                slope = Double.POSITIVE_INFINITY;
                yo = p2.x*1.0;
            }
            else
            {
                slope = 1.0*(p1.y-p2.y)/(p1.x-p2.x);
                yo =  p1.y-slope*p1.x;
            }
            pointsLine = new HashSet<Point>();
            addPoint(p1, p1Apearances);
            addPoint(p2, p2Apearances);
        }
        
        public void addPoint(Point p1, int nAppearances)
        {
            if(!pointsLine.contains(p1))
            {
                pointsLine.add(p1);
                nPoints+=nAppearances;
            }
        }
        
        public int getNumberPoints()
        {
            return nPoints;
        }
        
        public boolean equals(Object o)
        {
            if(!(o instanceof Line))
                return false;
            Line otherLine = (Line) o; 
            return otherLine.yo == yo && otherLine.slope == slope;
        }
        
        public int hashCode()
        {
            int hash = 3;
            hash = hash * 7 + Double.valueOf(yo).hashCode();
            hash = hash * 7 + Double.valueOf(slope).hashCode();
            return hash;
        }
    }
}

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;
    }
}