Algo Advance

Graph - Medium Level - Question 1 Leetcode 2049. Count Nodes With the Highest Score There is a binary tree rooted at 0 consisting of n nodes. The nodes are labeled from 0 to n - 1. You are given a 0-indexed integer array parents representing the tree, where parents[i] is the parent of node i. Since node 0 is the root, parents[0] == -1. Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees. Return the number of nodes that have the highest score. Constraints: n == parents.length 2 <= n <= 10^5 parents[0] == -1 0 <= parents[i] <= n - 1 for i != 0 parents represents a valid binary tree. Analysis: If we have had the binary tree, then we just can do a top-down count, to count the number of nodes for the sub-tree with the root as the curren...

Sweep (or scanning) line algorithm is very efficient for some specific questions involving discrete intervals. The intervals could be the lasting time of events, or the width of a building or an abstract square, etc. In the scanning line algorithm, we usually need to distinguish the start and the end of an interval. After the labeling of the starts and ends, we can sort them together based on the values of the starts and ends. Thus, if there are N intervals in total, we will have 2*N data points (since each interval will contribute 2). The sorting becomes the most time-consuming step, which is O(2N*log(2N) ~ O(N*logN). After the sorting, we usually can run a linear sweep for all the data points. If the data point is labeled as a starting point, it means a new interval is in the processing; when an ending time is reached, it means one of the interval has ended. In such direct way, we can easily figure out how many intervals are in the processes. Other related information can also be obt...

Binary Search - Hard Level - Question 1 Leetcode 410  Split Array Largest Sum Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. Constraints: 1 <= nums.length <= 1000 0 <= nums[i] <= 10^6 1 <= m <= min(50, nums.length) Analysis: This question seems not to be related with binary search, actually it does! The key argument is: if there is a value, say X, is the minimum of the largest sum among these m non-empty subarrays.  Then all the values below X cannot divide the array into m non-empty subarrays (should be larger than m).  Why? We can proof it by contradiction: if a value smaller than X, say Y, can be the minimum of the largest sum among these m non-empty subarrays, then X is NOT the minimum as claimed in the first sentence. Thus, there is no such Y existed. If all the values smaller than X ca...

Binary Search - Hard Level - Question 2 Leetcode 727 Minimum Window Subsequence Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W. If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index. Note: All the strings in the input will only contain lowercase letters. The length of S will be in the range [1, 20000]. The length of T will be in the range [1, 100]. Analysis: The first step to think about this question may be how to determine a string is a subsequence of another string?  We can use the two-pointer method: one is a pointer to the beginning of the first string and the other one is a pointer for the second string (to be matched). Once the second pointer can reach the end of the second string, it means we have found a subsequence in the first string. The time complexity for this step is O(...

 Question List: Question 1: Minimum Window Substring More Questions Upper Layer

Leetcode 76. Minimum Window Substring Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique. A substring is a contiguous sequence of characters within the string. Constraints: m == s.length n == t.length 1 <= m, n <= 10^5 s and t consist of uppercase and lowercase English letters. Analysis: The first step to do is to count the letters in string t, since the relative order of chars does not matter. After the counting, we can use two pointers method on string s: starting with beginning of the string s, the second pointer can continue to move until the sub-string [i, j) has all the chars in t, where i the index of the first pointer, and j is the index of the second pointer. We are looking for the sub-string with the minimum leng...

Sliding window is one common trick used in coding, which may not be counted as one "algorithm" by itself. Nevertheless, this trick is popular in tech code interviews, perhaps due to its relative "short" length (?). The size of the window could be either fixed or non-fixed, depends on the questions. When the size is non-fixed, two pointers are usually used to maintain the size of the window. Thus, the "two-pointer" method may be considered as a variant of the sliding window trick. The first point stands for the starting side of the "window" and the second one represents the ending side of the "window". When does the sliding window trick work? Usually string matching, or sub-array / sub-sequences may be considered to use the sliding window trick. The key point is that the question can be gradually solved by the evolution of the sliding window from the beginning of a string/array to the end. To sum up, sliding window 1. is a common trick i...