## Posts

Showing posts from January, 2021

### Distance in a Binary Tree - yet another space/time tradeoff Problem is here:  Find Distance in a Binary Tree - LeetCode 1740. Find Distance in a Binary Tree Medium 15 5 Add to List Share Given the root of a binary tree and two integers  p  and  q , return  the  distance  between the nodes of value  p  and value  q  in the tree . The  distance  between two nodes is the number of edges on the path from one to the other.   Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 0 Output: 3 Explanation: There are 3 edges between 5 and 0: 5-3-1-0. Example 2: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 7 Output: 2 Explanation: There are 2 edges between 5 and 7: 5-2-7. Example 3: Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 5 Output: 0 Explanation: The distance between a node and itself is 0.   Constraints: The number of nodes in the tree is in the range  [1, 10 4 ] . 0 <= Node.val <= 10 9 All  Node.val  are  unique . p  and  q  are values in the tree. With number of nodes = 10^4, you can't go for N

### Grid - Breadth First Search (BFS) - II Nothing gets more BFS'ish than this problem:  Shortest Path to Get Food - LeetCode 1730. Shortest Path to Get Food Medium 18 1 Add to List Share You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any food cell. You are given an  m x n  character matrix,  grid , of these different types of cells: '*'  is your location. There is  exactly one  '*'  cell. '#'  is a food cell. There may be  multiple  food cells. 'O'  is free space, and you can travel through these cells. 'X'  is an obstacle, and you cannot travel through these cells. You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle. Return  the  length  of the shortest path for you to reach  any  food cell . If there is no path for you to reach food, return  -1 .   Example 1: Input: grid = [["X","X","X","X","X","

### Combinatorial to reduce to N^2 This is an interesting problem:  Tuple with Same Product - LeetCode 1726. Tuple with Same Product Medium 109 5 Add to List Share Given an array  nums  of  distinct  positive integers, return  the number of tuples  (a, b, c, d)  such that  a * b = c * d  where  a ,  b ,  c , and  d  are elements of  nums , and  a != b != c != d .   Example 1: Input: nums = [2,3,4,6] Output: 8 Explanation: There are 8 valid tuples: (2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3) (3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2) Example 2: Input: nums = [1,2,4,5,10] Output: 16 Explanation: There are 16 valids tuples: (1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2) (2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1) (2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5) (4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2) Example 3: Input: nums = [2,3,4,6,8,12] Output: 40 Example 4: Input: nums = [2,3,5,7] Output: 0   Constraints: 1 <= nums.length <= 1000 1 <= nums[i] <= 10 4 All elements in  nums

### Rotten oranges, by LeetCode This is apparently a very popular coding interview question:  Rotting Oranges - LeetCode You are given an  m x n   grid  where each cell can have one of three values: 0  representing an empty cell, 1  representing a fresh orange, or 2  representing a rotten orange. Every minute, any fresh orange that is  4-directionally adjacent  to a rotten orange becomes rotten. Return  the minimum number of minutes that must elapse until no cell has a fresh orange . If  this is impossible, return   -1 .   Example 1: Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4 Example 2: Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally. Example 3: Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.   Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 10 grid[i][j]  is  0 ,  1 , or  2 . Ac

### Covid vaccination and the IBM Ponder This challenge This is the 6th IBM Ponder This that I manage to solve:  IBM Research | Ponder This | January 2021 Challenge . The challenge is copied/pasted below. This seems to be a straightforward problem where a DFS or BFS should do it. However, the challenge is the following: how to mark that a certain cell has been visited or not? There are no limits of how many times you can go thru one cell when it is marked as 2 or 3. This is the part that required some heuristic, at least from my part. First, to mark a cell as visited we need to make sure that the cell position, the cell value and the cell direction are all the same. Second, for the heuristic, I made an assumption that the robot can visit the same cell (with the mark mentioned before) at most N times. In terms of the execution time, for N = 50, we'll have something that is really expensive, but doable:  - Loop to find the first B: 50^2  - Loop to find the second B: 50^2  - Loop for the validation whether the vaccination is doable: 50^2

### Happy New Year! Easy problem by LC Hello Everyone, and Happy New Year to all of you, wishing you to stay safe and sound, and to have a kick-ass 2021 ahead. In other words, wishing that Happiness(2021) >> Happiness(2020). The first problem of the year seems computationally challenging, if it wasn't for one phrase . Here it is:  Largest Subarray Length K - LeetCode 1708. Largest Subarray Length K Easy 11 28 Add to List Share An array  A  is larger than some array  B  if for the first index  i  where  A[i] != B[i] ,  A[i] > B[i] . For example, consider  0 -indexing: [1,3,2,4] > [1,2,2,4] , since at index  1 ,  3 > 2 . [1,4,4,4] < [2,1,1,1] , since at index  0 ,  1 < 2 . A subarray is a contiguous subsequence of the array. Given an integer array  nums  of  distinct  integers, return the  largest  subarray of  nums  of length  k .   Example 1: Input: nums = [1,4,5,2,3], k = 3 Output: [5,2,3] Explanation: The subarrays of size 3 are: [1,4,5], [4,5,2], and [5,2,3]. Of these, [5,2,3] is the largest.