Frog Jump

A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.

If the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.

Note:

• The number of stones is ≥ 2 and is < 1,100.
• Each stone's position will be a non-negative integer < 2³¹.
• The first stone's position is always 0.

At first, I thought it'a a DP problem, but it's not. The confusion comes from the question Jump game. However, since we have the restriction that the frog can jump only k - 1, k or k + 1 stones, whether the frog can jump to current stone has no relation to if frog can jump to next stone. It's possible that the current jump is 4, and next distance is 2, so you cannot jump to that stone.

A better way is to use recursion. From the first stone, we calculate what's the next stone the frog can jump to, if we find one, recursively call the function to calculate the next stone we can jump to, exit when we reach the last stone.

If you simply follow this manner, you will have TLE. So how to optimize. Since we are calculating forwardly, it's possible the same stone and largest jump it has has been calculated before, and which is definitely not working (otherwise we exit the function). We can use a visited set to track all stone and jumps we had, if we already see the combination, we directly return false because we know it's not going to work.

public boolean canCross(int[] stones) {
        int len = stones.length;
        if (len <= 1) {
            return true;
        }
        if (len > 1 && stones[1] != 1) {
            return false;
        }
        Set visited = new HashSet<>();
        return checkCanCross(1, 1, stones, visited);
    }
    
    private boolean checkCanCross(int start, int dist, int[] stones, Set visited) {
        if (start >= stones.length - 1) {
            return true;
        }
        if (dist <= 0 || !visited.add(start + "," + dist)) {
            return false;
        }
        for (int i = start + 1; i < stones.length; i++) {
            int curr = stones[i] - stones[start];
            if (curr > dist + 1) {
                break;
            }
            if (curr == dist - 1 || curr == dist || curr == dist + 1) {
                if (checkCanCross(i, curr, stones, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note:
The number of people is less than 1,100.

Example

Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

This problem actually uses the easiest insert sort algorithm. We first sort the array with higher height and fewer people in the front:

[7,0] [7,1] [6,1][5,0][5,2][4,4]



Then we insert the array to correct index:

[7, 0][6,1][7, 1][5,0][5,2][4,4]

[5,0][7, 0][6,1][7, 1][5,2][4,4]

[5,0][7, 0][6,1][5,2][7, 1][4,4]

[5,0][7, 0][6,1][5,2][4,4][7, 1]


That's it.

public int[][] reconstructQueue(int[][] people) {
        if (people.length <= 1) {
            return people;
        }
        
        Arrays.sort(people, new Comparator<int[]>() {
           @Override
           public int compare(int[] first, int[] second) {
               if (first[0] != second[0]) {
                   return second[0] - first[0];
               } else {
                   return first[1] - second[1];
               }
           }
        });
        
        int len = people.length;
        for (int j = 1; j < len; j++) {
            int count = 0;
            int[] curr = people[j];
            for (int i = 0; i < j; i++) {
                if (count == curr[1]) {
                    for (int k = j - 1; k >= i; k--) {
                        people[k + 1] = people[k];
                    }
                    people[i] = curr;
                    break;
                } else {
                    if (people[i][0] >= people[j][0]) {
                        count++;
                    }
                }
            }
        }
        return people;
    }

Find Right Interval

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.

For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

1. You may assume the interval's end point is always bigger than its start point.
2. You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

Basically we need to sort the array, then for each interval, search all nodes to its right and find the first one that has start greater than its end. Searching for the first "right" node can have multiple ways, the most efficient way is to use binary search. But the easiest way is, to just traverse the nodes to its right and find the first right node.

I used a structure to track the original index of the interval. Alternatively we can also do it by using maps.

public int[] findRightInterval(Interval[] intervals) {
        int len = intervals.length;
        int[] rst = new int[len];
        if (len == 0) {
            return rst;
        }
        
        IntervalNode[] intervalNodes = new IntervalNode[len];
        int pos = 0;
        for (int i = 0; i < len; i++) {
            intervalNodes[pos++] = new IntervalNode(intervals[i], i);
        }
        
        Arrays.sort(intervalNodes, new Comparator() {
           @Override 
           public int compare(IntervalNode in1, IntervalNode in2) {
               if (in1.interval.start != in2.interval.start) {
                   return in1.interval.start - in2.interval.start;
               } else {
                   return in1.index - in2.index;
               }
           }
        });
        for (int i = 0; i < len; i++) {
            IntervalNode curr = intervalNodes[i];
            int end = curr.interval.end;
            int j = i + 1;
            
            while (j < len && curr.interval.end > intervalNodes[j].interval.start) {
                j++;
            }
            rst[curr.index] = j == len ? - 1 : intervalNodes[j].index;
        }
        return rst;
    }
    
    private class IntervalNode {
        Interval interval;
        int index;
        
        public IntervalNode(Interval interval, int index) {
            this.interval = interval;
            this.index = index;
        }
    }

Non-overlapping Intervals

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

1. You may assume the interval's end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]

Output: 1

Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input: [ [1,2], [1,2], [1,2] ]

Output: 2

Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input: [ [1,2], [2,3] ]

Output: 0

Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

For non-overlapping intervals, the start time should be larger than or equal to previous end time. Thus we sort the interval based on end time, then we initialize an end time to Integer.MIN_VALUE. After that, compare each interval's start time with the end time. If the start time is not smaller than "end time", we update the end time, this will be the latest time for all non-overlapping intervals. If the start time is smaller than the end time, we increment result, this is the interval we need to remove. The overall complexity should be O(nlogn) for sorting.

public int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        
        Arrays.sort(intervals, new Comparator () { 
            @Override
            public int compare(Interval i1, Interval i2) {
                if (i1.end != i2.end) {
                    return i1.end - i2.end;
                } else {
                    return i1.start - i2.start;
                }
            }
        });
        
        int rst = 0,  end = Integer.MIN_VALUE;
        for (Interval interval : intervals) {
            if (end <= interval.start) {
                end = interval.end;
            } else {
                rst++;
            }
        }
        return rst;
    }

Closest Binary search tree I && II

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target.

The first one is quite easy. Using binary search. The closest value should either be the root value or one of its children. Recursively get the closest value from the children and compare it with the root value.

public int closestValue(TreeNode root, double target) {
        if (root == null) {
            return -1;
        }
        return getClosestValue(root, target);
    }

    private int getClosestValue(TreeNode root, double target) {
        TreeNode kid = target < root.val ? root.left : root.right;
        if (kid == null) {
            return root.val;
        }
        int closest = getClosestValue(kid, target);
        double difference = Math.abs(root.val - target) - Math.abs(kid.val - target);
        return difference > 0 ? closest : root.val;
    }

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note: Given target value is a floating point. You may assume k is always valid, that is: k ≤ total nodes. You are guaranteed to have only one unique set of k values in the BST that are closest to the target. Follow up: Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

Consider implement these two helper functions: getPredecessor(N), which returns the next smaller node to N. getSuccessor(N), which returns the next larger node to N.

Using a priority queue. Recursively do an in order traversal and put nodes in the queue. If the size of the queue exceeds k, pull out the node with the largest difference.

public List<integer> closestKValues(TreeNode root, double target, int k) {
        List<integer> rst = new ArrayList<>();
        if (root == null) {
            return rst;
        }
        PriorityQueue<integer> queue = new PriorityQueue<>(k, new Comparator<integer>() {
            @Override public int compare(Integer o1, Integer o2) {
                double difference = Math.abs(o1.doubleValue() - target) - Math.abs(o2.doubleValue() - target);
                if (difference > 0) {
                    return -1;
                } else if (difference < 0) {
                    return 1;
                } else {
                    return 0;
                }
            }
        });
        getKValues(root, target, k, queue);
        while (!queue.isEmpty()) {
            rst.add(queue.poll());
        }
        return rst;
    }

    private void getKValues(TreeNode root, double target, int k, PriorityQueue queue) {
        if (root == null) {
            return;
        }
        getKValues(root.left, target, k, queue);
        queue.add(root.val);
        if (queue.size() > k) {
            queue.poll();
        }
        getKValues(root.right, target, k, queue);
    }

Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

Hint:

1. If a palindromic permutation exists, we just need to generate the first half of the string.
2. To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II orNext Permutation.

Count the occurrence of the string, if there are more than one odd number of occurrences in the string, return empty result. Otherwise start from middle and add chars to two sides until we reach the length.

public List<string> generatePalindromes(String s) {
        List<string> rst = new ArrayList<>();
        if (s.length() == 0) {
            return rst;
        }

        Map<character, integer> countChars = new HashMap<>();
        for (char c : s.toCharArray()) {
            if (!countChars.containsKey(c)) {
                countChars.put(c, 1);
            } else {
                countChars.put(c, countChars.get(c) + 1);
            }
        }
        char[] chars = new char[countChars.size()];
        char single = '$';
        int index = 0;
        boolean containsSingle = false;
        for (char c : countChars.keySet()) {
            if (countChars.get(c) % 2 != 0) {
                if (containsSingle) {
                    return rst;
                } else {
                    single = c;
                    containsSingle = true;
                }
            } else {
                chars[index++] = c;
            }
        }
        if (containsSingle) {
            getList(chars,  "" + single, rst, s.length(), chars.length - 1);
        } else {
            getList(chars, "", rst, s.length(), chars.length);
        }
        return rst;
    }

    private void getList(char[] chars,  String curr, List<string> rst, int length, int size) {
        if (curr.length() == length){
            rst.add(curr);
            return;
        }
        for (int i = 0; i < size; i++) {
            char c = chars[i];
            if (curr.indexOf(c) >= 0) {
                continue;
            }
            getList(chars, c + curr + c, rst, length, size);
        }
    }

Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

1. Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
2. According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

First, the graph should not contain cycle. Second, all nodes should connect to each other. The easiest way is to use union find. After all unions of edges, the size should be only 1.

    public boolean validTree(int n, int[][] edges) {
        UnionFind unionFind = new UnionFind(n);
        for (int[] e : edges) {
            if (!unionFind.union(e[0], e[1])) {
                return false;
            }
        }
        return unionFind.size == 1;

    }

    private class UnionFind {
        int[] vertices;
        int size = 0;

        public UnionFind(int n) {
            vertices = new int[n];
            Arrays.fill(vertices, -1);
            size = n;
        }
        public int find(int v) {
            validate(v);
            if (vertices[v] < 0) {
                return v;
            }
            vertices[v] = find(vertices[v]);
            return vertices[v];
        }

        public boolean union(int u, int v) {
            int uR = find(u);
            int vR = find(v);
            if (uR == vR) {
                return false;
            }
            if (vertices[vR] < vertices[uR]) {
                vertices[uR] = v;
            } else {
                if (vertices[vR] == vertices[uR]) {
                    vertices[uR]--;
                }
                vertices[vR] = u;
            }
            size--;
            return true;
        }

        private void validate(int v) {
            if (v < 0 || v >= vertices.length) {
                throw new InvalidParameterException("Invalid input!");
            }
        }
    }