Sunday, January 31, 2021

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

 

This is similar to question 235:

My answer: recursive 

Other solutions: non-recursion: use hash map to store node -> parent, and find all parents of p, q and find the lowest common one.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
        TreeNode rightResult = lowestCommonAncestor(root.right, p, q);

        if (leftResult == null && rightResult == null) {
            return null;
        } else if (leftResult == null) {
            return rightResult;
        } else if (rightResult == null) {
            return leftResult;
        } else {
            return root;
        }
    }
}



at No comments:

973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

 

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

 

Note:

  1. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000

 My answer: use max heap to keep track of smallest K elements, poll larger element every time when size is over K. O(N logk)

Other solutions can be quickselect,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    class Point {
        public int i;
        public int j;
        public double dist;
        public Point (int i, int j) {
            this.i = i;
            this.j = j;
            this.dist = Math.sqrt(i*i + j*j);
        }
    }
    public int[][] kClosest(int[][] points, int K) {
        if (points.length <= K) {
            return points;
        }
        // max heap
        PriorityQueue<Point> heap = new PriorityQueue<Point>((b, a) -> {return Double.compare(a.dist, b.dist);});
        for (int[] rawPoint : points) {
            Point point = new Point(rawPoint[0], rawPoint[1]);
            heap.add(point);
            if (heap.size() > K) {
                heap.poll();
            }
        }
        int[][] results = new int[K][2];
        for (int i = 0; i < K; i++) {
            Point point = heap.poll();
            results[i] = new int[]{point.i, point.j};
        }
        return results;
    }
}



at No comments:

244. Shortest Word Distance II

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list. Your method will be called repeatedly many times with different parameters. 

Example:
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3

Input: word1 = "makes", word2 = "coding"
Output: 1

Note:

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list. 

My answer: same as leetcode answer. Since indices1 and indices2 are already sorted, we just need to move i/j around so that indices1[i] and indices2[j] is always next to each. Once either one reaches end of list meaning 2 things: 1) if value of the other one is greater, we have already checked nearest ones in the other one, given the end value; 2) if value of the other one is smaller, we need to move the other indices until it is bigger than the end value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class WordDistance {

    Map<String, List<Integer>> wordIndices = new HashMap<String, List<Integer>>();
    public WordDistance(String[] words) {
        for (int i = 0; i < words.length; i ++) {
            List<Integer> indices = wordIndices.getOrDefault(words[i], new ArrayList<Integer>());
            indices.add(i);
            wordIndices.put(words[i], indices);
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> indices1 = wordIndices.getOrDefault(word1, new ArrayList<Integer>());
        List<Integer> indices2 = wordIndices.getOrDefault(word2, new ArrayList<Integer>());

        int i = 0;
        int j = 0;
        int minDistance = Integer.MAX_VALUE;
        while (i < indices1.size() && j < indices2.size()) {
            minDistance = Math.min(minDistance, Math.abs(indices1.get(i) - indices2.get(j)));
            if (indices1.get(i) > indices2.get(j)) {
                j ++;
            } else {
                i ++;
            }
        }
        return minDistance;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(words);
 * int param_1 = obj.shortest(word1,word2);
 */


at No comments:

671. Second Minimum Node In a Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node's value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree.

If no such second minimum value exists, output -1 instead.

 

 

Example 1:

Input: root = [2,2,5,null,null,5,7]
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

Example 2:

Input: root = [2,2,2]
Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 25].
  • 1 <= Node.val <= 231 - 1
  • root.val == min(root.left.val, root.right.val) for each internal node of the tree.

 My answer: recursion:

Better solution is put after it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        //find the 1st element larger than root
        if (root == null || root.left == null) {
            return -1;
        }
        int leftResult = findSecondMinimumValue(root.left);
        int rightResult = findSecondMinimumValue(root.right);

        int[] finalValues = new int[]{root.val, root.left.val, root.right.val, leftResult, rightResult};
        Arrays.sort(finalValues);
        for (int i = 0; i < finalValues.length; i ++) {
            if (finalValues[i] > root.val) {
                return finalValues[i];
            }
        }
        return -1;
    }
}



1
2
3
4
5
6
7
8
public int findSecondMinimumValue(TreeNode root) {
        if(root.left == null) return -1;
        
        int l = root.left.val == root.val ? findSecondMinimumValue(root.left) : root.left.val;
        int r = root.right.val == root.val ? findSecondMinimumValue(root.right) : root.right.val;
        
        return l == -1 || r == -1 ? Math.max(l, r) : Math.min(l, r);
    }


at No comments:

716. Max Stack

Design a max stack data structure that supports the stack operations and supports finding the stack's maximum element.

Implement the MaxStack class:

  • MaxStack() Initializes the stack object.
  • void push(int x) Pushes element x onto the stack.
  • int pop() Removes the element on top of the stack and returns it.
  • int top() Gets the element on the top of the stack without removing it.
  • int peekMax() Retrieves the maximum element in the stack without removing it.
  • int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.

 

Example 1:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

Explanation
MaxStack stk = new MaxStack();
stk.push(5);   // [5] the top of the stack and the maximum number is 5.
stk.push(1);   // [5, 1] the top of the stack is 1, but the maximum is 5.
stk.push(5);   // [5, 1, 5] the top of the stack is 5, which is also the maximum, because it is the top most one.
stk.top();     // return 5, [5, 1, 5] the stack did not change.
stk.popMax();  // return 5, [5, 1] the stack is changed now, and the top is different from the max.
stk.top();     // return 1, [5, 1] the stack did not change.
stk.peekMax(); // return 5, [5, 1] the stack did not change.
stk.pop();     // return 1, [5] the top of the stack and the max element is now 5.
stk.top();     // return 5, [5] the stack did not change.

 

Constraints:

  • -107 <= x <= 107
  • At most 104 calls will be made to push, pop, top, peekMax, and popMax.
  • There will be at least one element in the stack when pop, top, peekMax, or popMax is called.

 

Follow up: Could you come up with a solution that supports O(1) for each top call and O(logn) for each other call?  

My answer: stack + heap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class MaxStack {
    
    // alternative 1: use stack for max + normal stack, which always pushes max value everytime push(), 
    // it also pops when normal pop()/popMax() -> O(N)/O(N)
    // alternative 2: Double Linked List + TreeMap
    
    LinkedList<Integer> stack;
    PriorityQueue<Integer> heap;

    /** initialize your data structure here. */
    public MaxStack() {
        stack = new LinkedList<Integer>();
        heap = new PriorityQueue<Integer>((a, b) -> {return b.compareTo(a);});
    }
    
    public void push(int x) {
        stack.addLast(x);
        heap.add(x);
    }
    
    public int pop() {
        int removed = stack.removeLast();
        heap.remove(removed);
        return removed;
    }
    
    public int top() {
        return stack.peekLast();
    }
    
    public int peekMax() {
        return heap.peek();
    }
    
    public int popMax() {
        System.out.println(stack);
        int removed = heap.poll();
        int removeIndex = -1;
        for (int i = stack.size() - 1 ; i >= 0 ; i --) {
            if (stack.get(i) == removed) {
                removeIndex = i;
                break;
            }
        }
        stack.remove(removeIndex);
        System.out.println(stack);
        return removed;
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */


at No comments:

235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

 

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.


My answer: it is one important constraints that both p and q must exits. My answer works for any binary tree, even not BST

Better solution given BST: find the 1st node whose value is between p and q, starting from top-down direction. It is put after below answer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
        TreeNode rightResult = lowestCommonAncestor(root.right, p, q);

        if (leftResult == null && rightResult == null) {
            return null;
        } else if (leftResult == null) {
            return rightResult;
        } else if (rightResult == null) {
            return leftResult;
        } else {
            return root;
        }
    }
}

Solution for BST

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//         if (root == null || root == p || root == q) {
//             return root;
//         }
//         TreeNode leftResult = lowestCommonAncestor(root.left, p, q);
//         TreeNode rightResult = lowestCommonAncestor(root.right, p, q);

//         if (leftResult == null && rightResult == null) {
//             return null;
//         } else if (leftResult == null) {
//             return rightResult;
//         } else if (rightResult == null) {
//             return leftResult;
//         } else {
//             return root;
//         }
        if (p.val > q.val) {
            TreeNode temp = null;
            temp = p;
            p = q;
            q = temp;
        }
        if (root == null || (root.val >= p.val && root.val <= q.val)) {
            return root;
        }
        if (root.val >= q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (root.val <= p.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return null;
    }
}

 

at No comments: