Category: foundational_interview
-
LeetCode 1885: Count Pairs in Two Arrays
link Brute Force Check sum1 > sum2 Time: , space: . Check diff1 + diff2 > 0 We check against a modified version of the inequality: (nums1[i] – nums2[i]) + (nums1[j] – nums2[j]) > 0. An important difference is that outer loop is only handling the index i and the inner loop is only handling…
-
LeetCode 2089: Find Target Indices After Sorting Array
link Sort around pivot = target and along the way discover the range containing target. Time: , space: .
-
LeetCode 2389: Longest Subsequence With Limited Sum
link If we had nums sorted, we could compute its list of cumulative sums. For a query, its insert position in this list of cumulative sums would give the max length of subsequence for that query. Time: . Space: .
-
LeetCode 1385: Find the Distance Value Between Two Arrays
link For each element from arr1 try against all elements in arr2. If arr1 has elements and arr2 has elements, time: , space: . Insight: For a number in nums1, if the closest number in nums2 is and , then all other numbers in nums2 must also be more than distance away from . If…
-
LeetCode 2115: Find All Possible Recipes from Given Supplies
link We build a directed graph with vertex set as the union of recipes and ingredients. An edge represents . A topological order of recipes from this graph will give us the recipes we can make. We use in-degree approach. Say we start with supplies as the sources, therefore vertices with in-degree = 0. Then…
-
LeetCode 2246: Longest Path With Different Adjacent Characters
link If we had a simpler tree where for edge , s[u] != s[v], then our problem would be finding the length of the longest path in the tree. We can reduce the original problem to the above simpler problem by building an undirected graph having an edge only between different char’s. This is equivalent…
-
LeetCode 2392: Build a Matrix With Conditions
link The row indices of the numbers must be a permutation of row indices . Say we only have rowConditions — no conditions on the columns. We can build a directed graph with vertex set and edge set . Then, from a topological ordering of , we can find a valid permuation of row indices…
-
LeetCode 210: Course Schedule II
We build a directed graph where vertex set is the courses and an edge represents . So, input [0, 1] would be added as the edge . If the graph does not have a cycle, it is a DAG and we emit the courses in topological order. DFS Presence of back edge signals cycle in…
-
LeetCode 207: Course Schedule
link Check if the directed graph has cycle. An edge represents . In the input, [0, 1] means 1 has to be done before 0. So, we add edge in our graph. DFS Check if graph has back edge. Time and space complexity is that of DFS: . In-degree Check if all courses can be…
-
LeetCode 953: Verifying an Alien Dictionary
link Lexicographic order between two words can be thought of as comparing two same-length numbers with the shorter one padded with ‘s on the right. Since for three numbers , if and , then ; lexicographic order is transitive. Validating pairs of consecutive words is thus sufficient. With words, alphabet size , and the biggest…
unreasonably effective 