Algo Advance

Most Beautiful Item for Each Query You are given a 2D integer array items where items[i] = [pricei, beautyi] denotes the price and beauty of an item respectively. You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0. Return an array answer of the same length as queries where answer[j] is the answer to the jth query. Constraints: 1 <= items.length, queries.length <= 10^5 items[i].length == 2 1 <= pricei, beautyi, queries[j] <= 10^9 Analysis: The first step can be to sort the items based on the price. Then we can narrow down the search range by a binary search. But the beauty is not sorted yet. So if without further treatment, we need to scan through the query range, the time complexity is O(N). The query length could be as large as 1e5, thus the overall time complexity is O(N*M) ~ 1e10, which is ...

Segment Tree - Question List Question 1:  Most Beautiful Item for Each Query More Questions Upper Layer

Segment tree can be viewed as an abstract data structure which using some more space to trade for speed. For example, for a typical question with O(N^2) time complexity, the segment tree method can decrease it to O(N*log(N)).  To make it understandable, let us consider one example. Say we have an integer array of N size, and what we want is to query the maximum with a query range [idx1, idx2], where idx1 is the left indexes, and idx2 is the right indexes inclusive. If we only do this kind of query once, then we just need to scan through the array from idx1 to idx2 once, and record the maximum, done. The time complexity is O(N), which is decent enough in most cases even though it is not the optimal one (for example, with a segment tree built, the time complexity can decrease down to O(log(N))). However, how about we need to query the array N times? If we continue to use the naïve way above, then the time complexity is O(N^2), since for each query we need to scan the query range once...

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(...