Algo Advance

2392. Build a Matrix With Conditions You are given a positive integer k. You are also given: a 2D integer array rowConditions of size n where rowConditions[i] = [abovei, belowi], and a 2D integer array colConditions of size m where colConditions[i] = [lefti, righti]. The two arrays contain integers from 1 to k. You have to build a k x k matrix that contains each of the numbers from 1 to k exactly once. The remaining cells should have the value 0. The matrix should also satisfy the following conditions: The number abovei should appear in a row that is strictly above the row at which the number belowi appears for all i from 0 to n - 1. The number lefti should appear in a column that is strictly left of the column at which the number righti appears for all i from 0 to m - 1. Return any matrix that satisfies the conditions. If no answer exists, return an empty matrix. Constraints: 2 <= k <= 400 1 <= rowConditions.length, colConditions.length <= 10^4 rowConditions[i].length == c...

2337. Move Pieces to Obtain a String You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where: The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right. The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces. Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false. Constraints: n == start.length == target.length 1 <= n <= 10^5 start and target consist of the characters 'L', 'R', and '_'. Analysis: The n could be pretty large, so we need to find an algorithm either O(N) or O(Nlog(N)). Some key observations: 1. th...

Question List Question 1:  167. Two Sum II - Input Array Is Sorted Question 2:  2337. Move Pieces to Obtain a String Upper Layer

167. Two Sum II - Input Array Is Sorted Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space. Constraints: 2 <= numbers.length <= 3 * 104 -1000 <= numbers[i] <= 1000 numbers is sorted in non-decreasing order. -1000 <= target <= 1000 The tests are generated such that there is exactly one solution. Analysis: The array is sorted, so we may want to consider binary search, but actually we can use a two-pointer method to quickly solve this problem, which is faster than the binary searc...

Double Pointers is one of the common tricks used in algorithm interviews. For some circumstances, for example, one or two sorted arrays, we can use two pointers to track the loop process. The final answer can be updated during the looping, and obtained when the loop is done. The logic behind the double pointers is that for every step, we just need to move one of the two pointers, or two of them. The optimal or final answer can be converged by doing this. Thus the time complexity is linear, and the space complexity is constant. One of the key step is that we have to make sure (or proof) by moving the two pointers, we will not miss the possible local optimal solutions, which then guarantees that we will obtain the global optimal solutions after finishing the looping. Question List Upper Layer

692. Top K Frequent Words Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order. Constraints: 1 <= words.length <= 500 1 <= words[i] <= 10 words[i] consists of lowercase English letters. k is in the range [1, The number of unique words[i]] Analysis: This question is quite straightforward. We can use a priority_queue to keep the top K valid elements. One difficulty may be about the comparator of the priority_queue.  In C++, the default order of the priority_queue is with the largest one on the top. But in this question, we need choose the top K with the largest count, so we need a reversed priority_queue. And more, for the same count, we need to choose the one with the lexicographical order. So we need to take care of this in the comparator. See the code below: class Solution { public: typedef pair<...

2246. Longest Path With Different Adjacent Characters You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i. Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them. Constraints: n == parent.length == s.length 1 <= n <= 10^5 0 <= parent[i] <= n - 1 for all i >= 1 parent[0] == -1 parent represents a valid tree. s consists of only lowercase English letters. Analysis For this question, we need to construct a graph, or more specifically, a n-nary tree. How to construct the graph/tree? What we only know is the parent array. So we need to go through the parent array and constr...

 2192. All Ancestors of a Node in a Directed Acyclic Graph You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph. Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order. A node u is an ancestor of another node v if u can reach v via a set of edges. Constraints: 1 <= n <= 1000 0 <= edges.length <= min(2000, n * (n - 1) / 2) edges[i].length == 2 0 <= fromi, toi <= n - 1 fromi != toi There are no duplicate edges. The graph is directed and acyclic. Analysis: This question can be solved by constructing a graph by the edges information. Since this question asks for the parents information, we can create a graph storing the direct parents notes.  After having the graph,...

Depth-first-search - medium level - question 2 2115. Find All Possible Recipes from Given Supplies You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes. You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them. Return a list of all the recipes that you can create. You may return the answer in any order. Note that two recipes may contain each other in their ingredients. Constraints: n == recipes.length == ingredients.length 1 <= n <= 100 1 <= ingredients[i].length, supplies.length <= 100 1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10 recipes[i...

1316. Distinct Echo Substrings Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string). Constraints: 1 <= text.length <= 2000 text has only lowercase English letters. Analysis: There are O(N^2) substring in total, and if we check each substring one by one, the time complexity for checking is O(N). So the overall time complexity is O(N^3). The longest test case may have N as 2000, so N^3 ~ 10^10, which is too large. We need to find some other ways faster. One way is to use a rolling hashing method. For a fixed length, we just scan the string from left to right once with double pointers. The first pointer is the ending of the first half; the second one is the ending of the second half. If they are the same, or give the same hash value, then we consider they are the same. To avoid repeating counting, we can use a set. See the code below, class Solution { pu...

2156. Find Substring With Given Hash Value The hash of a 0-indexed string s of length k, given integers p and m, is computed using the following function: hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m. Where val(s[i]) represents the index of s[i] in the alphabet from val('a') = 1 to val('z') = 26. You are given a string s and the integers power, modulo, k, and hashValue. Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue. The test cases will be generated such that an answer always exists. A substring is a contiguous non-empty sequence of characters within a string. Constraints: 1 <= k <= s.length <= 2 * 104 1 <= power, modulo <= 109 0 <= hashValue < modulo s consists of lowercase English letters only. The test cases are generated such that an answer always exists. Analysis This is question is about rolling hash. The formula is given, but we cannot use it directly. Or ...

Rolling Hash - Question List Question 1.  2156. Find Substring With Given Hash Value Question 2.  1316. Distinct Echo Substrings Upper Layer

Rolling hash is one common trick used to increase efficiency of substring comparisons by compressing (or hashing) a string into a integer. After this step, we can compare two strings directly without comparing each chars. So the efficiency can be increased from O(N) to O(1). So how to implement the rolling hash? First we need to choose a base for the expansion and a modulo to mod. The basic formula is (suppose the window is n, and the rolling direction is from left to right), HashVal = (A1*p^(n-1) + A2*p^(n-2) + ... + An-1*p^1 + An*p^0)%mod where HashVal is the hash value, Ai is the ith element, p is the base, and mod is the modulo. To avoid collision as much as we can, p and modulo usually need to be large prime numbers. One corner case is that the base order in the above formula cannot be reversed. Or to be more clear, if the rolling direction is from left to right in an array, the first element should be in the highest order of the base, or times p^(n-1), and the last element times ...

Recursion - Medium Level - Question 2 Leetcode 1922  Count Good Numbers A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7). For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even. Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 10^9 + 7. A digit string is a string consisting of digits 0 through 9 that may contain leading zeros. Constraints: 1 <= n <= 10^15 Analysis: One of the keys is how to keep the question still the "same question". It is clear that for this question, the total number is "5 * 4 * 5 * 4 * 5 * 4 ...", which are apparently repetitive operations. So we do not need to calculate it one by one, which is NOT the most eff...

Recursion - Interview Questions - Question 2 Please reverse a singly linked list using a recursion method. Analysis: We can view the reverse process in a three steps: 1. sperate the first element from the rest ones; 2. recursively reverse the rest ones; 3. connect the reversed rest linked list with the former first element (which become the last one now). See the code below: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if(!head||!head->next) return head; ListNode* p=head; // recursive call head=reverseList(p->next); // the former second element becomes the last second one, and // needs to pointe to the former head (to be the last one) p->next->next=p; // make the former head to be the last one p->next=NULL; retur...

Recursion - Easy Level - Question 2 Question 2 Leetcode 509  Fibonacci Number The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. Given n, calculate F(n). Constraints: 0 <= n <= 30 Analysis: 1. the base case is obvious: F(0) and F(1); 2. the converging formula is given directly as well; So just need to convert them into code. See the code below: class Solution { public: int fib(int N) { if(N<2) return N; return fib(N-1) + fib(N-2); } }; But if you have learned some algorithm before and had some understanding of time and space complexity, you can immediately realize that the above method is NOT the most efficient one. The reason is that we re-calculated so many inter-mediates many times! For example, fib(N-2) was calculated when calculating fib(N-1), which was...

Dynamic Programming - Medium Level - Question 2 Leetcode 174  Dungeon Game The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess. The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately. Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers). To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step. Return the knight's minimum initial health so that he can rescue the princess. Note that any room ca...

Dynamic Programming - Easy Level - Question 2 Leetcode 62  Unique Paths A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Constraints: 1 <= m, n <= 100 It's guaranteed that the answer will be less than or equal to 2 * 10^9. Analysis: We can apply the same idea in Question1 to the current one, which is from 1D to 2D. One of the key information is: the robot can only go down or right. So if we define f[i][j] means the total number of ways to reach this position, then f[i][j] = f[i-1][j] + f[i][j-1] The first term on the right side is for "go right", and the second for "go down". After having the state definition and transition formula, we just need to figure out the initial states' ...

Breadth-first Search - Hard - Question 1 815. Bus Routes You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever. For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever. You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only. Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible. Constraints: 1 <= routes.length <= 500. 1 <= routes[i].length <= 10^5 All the values of routes[i] are unique. sum(routes[i].length) <= 10^5 0 <= routes[i][j] < 10^6 0 <= source, target < 10^6 Analysis: One of key steps to this question is to build the connections. For example, once we start with the source stop, then we know what is the next stops to go. Wi...

1674. Minimum Moves to Make Array Complementary You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive. The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5. Return the minimum number of moves required to make nums complementary. Constraints: n == nums.length 2 <= n <= 10^5 1 <= nums[i] <= limit <= 10^5 n is even. Analysis: The brute force method works, for example, the pair sum range is [2, limit*2], so we can check the number of replacements needed for each sum, then pick up the smallest one. But the time complexity is O(N*limit), which could be as high as 10^10! So we need to find a faster method to pass the OJ. A faster algorithm is NOT easy to find, if do not have a good underst...