[LeetCode] 1026. Maximum Difference Between Bode and Ancestor

 Problem : https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

Calculate the difference of node.val and the maximum and minimum value from its child trees.

Time complexity = O(N), N = total nodes of the given tree.

/**
 * 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 maxAncestorDiff(TreeNode root) {
        return postOrder(root)[2];
    }
    
    int[] postOrder(TreeNode node) {
        int mi = node.val;
        int mx = node.val;
        int diff = 0;
        
        for (TreeNode child: new TreeNode[] {node.left, node.right}) {
            if (child != null) {
                // mi, mx, diff
                int[] tmp = postOrder(child);
                
                mi = Math.min(mi, tmp[0]);
                mx = Math.max(mx, tmp[1]);
                
                diff = Math.max(diff, tmp[2]); 
                diff = Math.max(diff, Math.abs(node.val - tmp[0]));
                diff = Math.max(diff, Math.abs(node.val - tmp[1])); 
            }
        }
        
        return new int[] {mi, mx, diff};
    }
}

[LeetCode] 876. Middle of the Linked List

 Problem : https://leetcode.com/problems/middle-of-the-linked-list/

The fast and slow pointer approach :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while (fast != null  && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
    }
}

[LeetCode] 973. K Closest Points to Origin

 Problem : https://leetcode.com/problems/k-closest-points-to-origin/

Use max priority queue to find the K closest points.

Time complexity = O( N * Log K ),  N = length of the input array. 

Space complexity = O ( K ),  the priority queue will contain at most K elements.

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // create a max priority queue for saving the K closest points
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> distanceOf(b) - distanceOf(a));
        
        for (int i = 0; i < points.length; i++) {
            if (pq.size() < k) {
                // put the point into the priority queue if the queue size is less than K
                pq.offer(points[i]);
            } else if (distanceOf(pq.peek()) > distanceOf(points[i])) {
                // otherwise, add the new point into priority queue if it is closer than the top point.
                // because it is max priority queue, the top point is the furthest point so far.
                // this condition check is needed to avoid blindly adding new point inito priority queue.
                pq.poll();
                pq.offer(points[i]);
            }
        }
    
        return pq.toArray(new int[0][]);
    }
    
    int distanceOf(int[] p) {
        return p[0] * p[0] + p[1] * p[1];
    }
}

Quick Selection solutioin.

Time complexity = O(N)

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        return quickSelect(points, 0, points.length-1, k);
    }
    
    int[][] quickSelect(int[][] points, int left, int right, int k) {       
        while (left < right) {
            int p = partition(points, left, right);
            if (p == k-1) {
                break;
            }
            
            if (p < k-1) {
                // continue to sort the rang [p+1, right]
                left = p + 1;
            } else {
                // continue to sort the range [left, p-1]
                right = p - 1;
            }
        }
        
        return Arrays.copyOf(points, k); 
    }
    
    int partition(int[][] points, int left, int right) {
        // use points[left] as the pivot value
        int pivotDistance = distanceOf(points[left]);
        
        int i = left, j = right + 1; // left and right scan indices
        
        while (true) {
            // scan left, stop when points[i] > pivotDistance or i reaches the array end
            while (distanceOf(points[++i]) < pivotDistance) if (i == right) break;
            // scan right, stop when points[j] < pivotDistance or j reaches the array start
            while (distanceOf(points[--j]) > pivotDistance) if (j == left) break;
            
            // stop scan
            if (i >= j) break;
            
            // exchange i and j
            int[] tmp = points[j];
            points[j] = points[i];
            points[i] = tmp;
        }
        
        // points[j] is the last element on right smaller than points[left]
        // swap 'left' and 'j'
        int[] tmp = points[left];
        points[left] = points[j];
        points[j] = tmp;
        
        return j;
    }
    
    int distanceOf(int[] p) {
        return p[0] * p[0] + p[1] * p[1];
    }
}

Edited on 12/26/2021. Add the quick select solution.

I got the 2021 annual medal badge

[LeetCode] 1200. Minimum Absolute Difference

 Problem : https://leetcode.com/problems/minimum-absolute-difference/

Because the minimum difference can only exist between 2 consecutive elements in sorted list.

We sort the input array first, then find the pairs with minimum difference.

Time complexity = O(N * LogN) + O(N),  N = length of the input array.

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int miGlobal = Integer.MAX_VALUE;
        List<List<Integer>> result = new ArrayList();
        
        // minimum absolute difference can only exist between 2 consecutive elements
        Arrays.sort(arr);
        
        for (int i = 1; i < arr.length; i++) {
            int miLocal = arr[i] - arr[i-1];
            if (miLocal < miGlobal) {
                // start a new result when find a new minimum difference
                miGlobal = miLocal;
                result = new ArrayList(Arrays.asList(Arrays.asList(arr[i-1], arr[i])));
            } else if (miLocal == miGlobal) {
                // otherwise append this new pair to the result list.
                result.add(Arrays.asList(arr[i-1], arr[i]));
            }
        }
        
        return result;
    }
}

Because the value range of the input array is from -10^6 to 10^6, the input array can be sorted with counting sort approach which Time complexity is O(N)

[LeetCode] 394. Decode String

 Problem : https://leetcode.com/problems/decode-string/

Use 2 stacks to decode. One stack save the counter. Another stack save of the decoded string of current level.

Time Complexity = O ( N * K ),  N = length of the input string. K = maximum value of the counter .

class Solution {
    public String decodeString(String s) {
        // save the decoded string
        // use StringBuilder to avoid repeatedly creating string object
        Stack<StringBuilder> strStack = new Stack();
        // save the counter of decoded string
        Stack<Integer> counterStack = new Stack();
        
        strStack.push(new StringBuilder());
        int count = 0;
        
        for (Character a: s.toCharArray()) {            
            if (Character.isDigit(a)) {
                // important!  counter k may have more than one digits!
                count = count * 10 + (a - '0');
            } else if (a == '[') {
                // push the counter
                counterStack.push(count);
                // push a new string builder to start a new level
                strStack.push(new StringBuilder());
                // reset the counter
                count = 0;
            } else if (a == ']') {
                // current level decoded string
                String decoded = strStack.pop().toString(); 
                // count of current level decoded string
                int n = counterStack.pop();
                
                // append the decoded string to its upper level string
                for (int j = 0; j < n; j++) {
                    strStack.peek().append(decoded);
                }
            } else {
                // append the character to current level string
                strStack.peek().append(String.valueOf(a));
            }
        }
        
        return strStack.peek().toString();
    }
}

[LeetCode] 938. Range Sum of BST

 Problem : https://leetcode.com/problems/range-sum-of-bst/

Use BST property to trim branches outside of the range.

/**
 * 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 rangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        // left subtree and current node are out of the range
        if (root.val < low)  return rangeSumBST(root.right, low, high);
        // right subtree and current node are out of the range
        if (root.val > high) return rangeSumBST(root.left, low, high);
        // current node is inside of the range
        return rangeSumBST(root.left, low, high) + root.val + rangeSumBST(root.right, low, high);
    }
}

[LeetCode] 1306. Jump Game III

Problem : https://leetcode.com/problems/jump-game-iii/

A typical BFS problem. In case it encounters a loop during the traversal, it is impossible to reach to the position with value 0.

Time complexity = O ( N ).   N = length of the arr. Because we need to every item in the input array at least once.

class Solution {
    public boolean canReach(int[] arr, int start) {
        if (arr[start] == 0) return true;
        
        int N = arr.length;
        boolean[] visited = new boolean[N];
        visited[start] = true;
        
        Queue<Integer> queue = new LinkedList();
        queue.offer(start);
        
        int[] diffs = new int[] {1, -1};
        
        while (!queue.isEmpty()) {
            int index = queue.poll();
                        
            for (int d : diffs) {
                int next  = index + d * arr[index];
                if (next >= 0 && next < N && !visited[next]) {
                    if (arr[next] == 0) return true;

                    visited[next] = true;
                    queue.offer(next);
                }
            }
        }
        
        return false;
    }
}

[LeetCode] 1032. Stream of Characters

 Problem : https://leetcode.com/problems/stream-of-characters/

This is an obvious Tire problem. It is difficult because it is hard to realize the edge cases at the first place.

We cannot assume one input word cannot be prefix of another input word.

Such as:  ["ab","ba","aaab","abab","baa"]

To cover all cases, we need to remember the last pointer of all valid prefixes.

class TrieNode {
    char letter = 0;
    boolean end = false;
    HashMap<Character, TrieNode> children = new HashMap();
}

class StreamChecker {
    TrieNode root = new TrieNode();
    Queue<TrieNode> queue = new LinkedList();
    
    public StreamChecker(String[] words) {
        for (int i = 0; i < words.length; i++) {
            TrieNode p = root;
            
            for (int j = 0; j < words[i].length(); j++) {
                if (p.children.containsKey(words[i].charAt(j))) {
                    p = p.children.get(words[i].charAt(j));
                } else {
                    TrieNode tmp = new TrieNode();
                    tmp.letter = words[i].charAt(j);
                    p.children.put(words[i].charAt(j), tmp);
                    p = tmp;
                }
            }
            
            p.end = true;
        }
    }
    
    public boolean query(char letter) {
        queue.offer(root);
        
        boolean found = false;
        Queue<TrieNode> next = new LinkedList();
        
        while (!queue.isEmpty()) {
            TrieNode p = queue.poll();
            
            if (p.children.containsKey(letter)) {
                next.offer(p.children.get(letter));
                if (p.children.get(letter).end) {
                    found = true;
                }
            }
        }
        
        queue = next;
        return found;
    }
}

However this process is not optimized.

A better solution is saving the prefixes backwards in Trie. Because all potential valid prefixes end with the same letter.

class TrieNode:
    def __init__(self, w = None):
        self.w = w
        self.children = {}
        self.end = False

class StreamChecker:

    def __init__(self, words: List[str]):
        self.root = TrieNode()
        self.max_len = 0
        self.stream = deque()
        
        for word in words:
            self.max_len = max(self.max_len, len(word))
            
            p = self.root
            
            for w in word[::-1]:
                if w not in p.children:
                    trie = Trie(w)
                    p.children[w] = trie
                    p = trie
                else:
                    p = p.children[w]
            
            p.end = True
                      

    def query(self, letter: str) -> bool:
        self.stream.append(letter)
        
        while len(self.stream) > self.max_len:
            self.stream.popleft()
        
        p = self.root
        
        for w in reversed(self.stream):
            
            if w in p.children:
                p = p.children[w]
                if p.end:
                    return True
            else:
                return False
                
        return False