Another Casual Coder

I find the strategy to solving this problem an instance of the famous programming pattern "Map-Reduce", where you use step one to map a sparse subset of potential solutions to your problem, followed by a reduction of that subset into the actual solution. The map in this case calculates the distance from a node to all the other nodes using a queue and BFS. The reduce simply goes to the two calculated distance arrays and retrieves the solution in linear time. Code is down below, cheers, ACC. Find Closest Node to Given Two Nodes - LeetCode 2359. Find Closest Node to Given Two Nodes Medium 147 44 Add to List Share You are given a  directed  graph of  n  nodes numbered from  0  to  n - 1 , where each node has  at most one  outgoing edge. The graph is represented with a given  0-indexed  array  edges  of size  n , indicating that there is a directed edge from node  i  to node  edges[i] . If there is no o...

This actually is a simpler problem then it looks. Given the limit for N is O(10^2), an N^3 solution brings us to O(10^6), which is very tractable. Three nested loops (and a hash table) would do it. Code is down below, cheers, ACC. Equal Row and Column Pairs - LeetCode 2352. Equal Row and Column Pairs Medium 205 3 Add to List Share Given a  0-indexed   n x n  integer matrix  grid ,  return the number of pairs  (R i , C j )  such that row  R i  and column  C j  are equal . A row and column pair is considered equal if they contain the same elements in the same order (i.e. an equal array).   Example 1: Input: grid = [[3,2,1],[1,7,6],[2,7,7]] Output: 1 Explanation: There is 1 equal row and column pair: - (Row 2, Column 1): [2,7,7] Example 2: Input: grid = [[3,1,2,2],[1,4,4,5],[2,4,2,2],[2,4,2,2]] Output: 3 Explanation: There are 3 equal row and column pairs: - (Row 0, Column 0): [3,1,2,2] - (Row 2, Column 2): [2,4,2,2] - ...

Gauss is one the most brilliant mathematicians to have ever lived. The formula for the summation that he discovered when he was only 10y old is used everyday today but hundreds of thousands of people, sometimes not even aware that they are using the formula discovered by a 10y old kid. Problem below requires this formula. Count the number of consecutive zeroes (use a simple finite-state-machine technique) and then apply Gauss' formula. Watch out for overflows (use long instead of int). Code is down below, cheers, ACC. Number of Zero-Filled Subarrays - LeetCode 2348. Number of Zero-Filled Subarrays Medium 31 2 Add to List Share Given an integer array  nums , return  the number of  subarrays  filled with  0 . A  subarray  is a contiguous non-empty sequence of elements within an array.   Example 1: Input: nums = [1,3,0,0,2,0,0,4] Output: 6 Explanation: There are 4 occurrences of [0] as a subarray. There are 2 occurrences of [0,0] as a subarr...

Since the goal of LC is to learn, there is nothing wrong in following the hints whenever you get stuck. I got stuck in the problem below and took a look at the hints: pick any node, find the farthest  node A from it, now find the farthest  node B from A, and you have your answer. Clever, but I couldn't figure that out on my own. Still was left to implement the code. Down below, cheers, ACC. Tree Diameter - LeetCode 1245. Tree Diameter Medium 649 16 Add to List Share The  diameter  of a tree is  the number of edges  in the longest path in that tree. There is an undirected tree of  n  nodes labeled from  0  to  n - 1 . You are given a 2D array  edges  where  edges.length == n - 1  and  edges[i] = [a i , b i ]  indicates that there is an undirected edge between nodes  a i  and  b i  in the tree. Return  the  diameter  of the tree .   Example 1: Input: edges = [...

IComparer can be used with BigInteger too which makes it very handy for problems like this one. Notice that the only reason to use IComparer is that the sorting is conditional when the two elements are the same (in this case we need to use the elements' indexes). Other than that, just follow exactly what the problem description says - since the constraints of the problem are very small, execution time won't suffer as much despite the time complexity being of O(N^2 * NLogN). N is very small (10^2), hence this reduces to N^3, or one million. Code is down below, cheers, ACC. Query Kth Smallest Trimmed Number - LeetCode 2343. Query Kth Smallest Trimmed Number Medium 86 235 Add to List Share You are given a  0-indexed  array of strings  nums , where each string is of  equal length  and consists of only digits. You are also given a  0-indexed  2D integer array  queries  where  queries[i] = [k i , trim i ] . For each  queries[i] , you...

An interesting problem that can be solved with a linear scan and storing just the two max numbers. Code below, cheers, ACC. Max Sum of a Pair With Equal Sum of Digits - LeetCode 2342. Max Sum of a Pair With Equal Sum of Digits Medium 57 1 Add to List Share You are given a  0-indexed  array  nums  consisting of  positive  integers. You can choose two indices  i  and  j , such that  i != j , and the sum of digits of the number  nums[i]  is equal to that of  nums[j] . Return  the  maximum  value of  nums[i] + nums[j]  that you can obtain over all possible indices  i  and  j  that satisfy the conditions.   Example 1: Input: nums = [18,43,36,13,7] Output: 54 Explanation: The pairs (i, j) that satisfy the conditions are: - (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54. - (1, 4), both numbers have a sum of digits equal to 7, and their ...

Solution to this problem requires an FSM. The FSM controls the direction to which either the row or the column should move. Control the outer-loop based on the current list node. Time complexity then becomes 4 * 10^5. Code is down below, cheers, ACC. Spiral Matrix IV - LeetCode 2326. Spiral Matrix IV Medium 151 8 Add to List Share You are given two integers  m  and  n , which represent the dimensions of a matrix. You are also given the  head  of a linked list of integers. Generate an  m x n  matrix that contains the integers in the linked list presented in  spiral  order  (clockwise) , starting from the  top-left  of the matrix. If there are remaining empty spaces, fill them with  -1 . Return  the generated matrix .   Example 1: Input: m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0] Output: [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]] Explanation: The diagram above shows how the values are printed in the matr...