Another Casual Coder

Problem is here:  https://leetcode.com/problems/closest-binary-search-tree-value-ii/ 272. Closest Binary Search Tree Value II Hard 524 18 Add to List Share Given a non-empty binary search tree and a target value, find  k  values in the BST that are closest to the target. Note: Given target value is a floating point. You may assume  k  is always valid, that is:  k  ≤ total nodes. You are guaranteed to have only one unique set of  k  values in the BST that are closest to the target. Example: Input: root = [4,2,5,1,3], target = 3.714286, and k = 2 4 / \ 2 5 / \ 1 3 Output: [4,3] Follow up: Assume that the BST is balanced, could you solve it in less than  O ( n ) runtime (where  n  = total nodes)? Accepted 50,428 Submissions 103,444 I managed to solve this problem in NLogN. Initially I thought this would not work since the problem is suggesting a less-than O(n) solution, but I gave it a try anyways. To solve in NLogN one appro

Problem is here:  https://leetcode.com/problems/validate-binary-tree-nodes/ 1361. Validate Binary Tree Nodes Medium 47 2 Add to List Share You have  n  binary tree nodes numbered from  0  to  n - 1  where node  i  has two children  leftChild[i]  and  rightChild[i] , return  true  if and only if  all  the given nodes form  exactly one  valid binary tree. If node  i  has no left child then  leftChild[i]  will equal  -1 , similarly for the right child. Note that the nodes have no values and that we only use the node numbers in this problem. Example 1: Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true Example 2: Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] Output: false Example 3: Input: n = 2, leftChild = [1,0], rightChild = [-1,-1] Output: false Example 4: Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1] Output: false Constraints: 1 <= n <= 10^4 leftChild.

This is a problem that seems to be suitable for breaking into three clear parts  https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/ 1123. Lowest Common Ancestor of Deepest Leaves Medium 194 275 Add to List Share Given a rooted binary tree, return the lowest common ancestor of its deepest leaves. Recall that: The node of a binary tree is a  leaf  if and only if it has no children The  depth  of the root of the tree is 0, and if the depth of a node is  d , the depth of each of its children is  d+1 . The  lowest common ancestor  of a set  S  of nodes is the node  A  with the largest depth such that every node in S is in the subtree with root  A . Example 1: Input: root = [1,2,3] Output: [1,2,3] Explanation: The deepest leaves are the nodes with values 2 and 3. The lowest common ancestor of these leaves is the node with value 1. The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]". Example 2: Inp

Problem is here:  https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/ 1026. Maximum Difference Between Node and Ancestor Medium 313 17 Add to List Share Given the  root  of a binary tree, find the maximum value  V  for which there exists  different  nodes  A  and  B  where  V = |A.val - B.val|  and  A  is an ancestor of  B . (A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.) Example 1: Input: [8,3,10,1,6,null,14,null,null,4,7,13] Output: 7 Explanation: We have various ancestor-node differences, some of which are given below : |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7. Note: The number of nodes in the tree is between  2  and  5000 . Each node will have value between  0  and  100000 . An N^2 approach seems at a glance to be the most logical approach: for each node, do a DFS travers

Problem is here, has to deal with Zeroes. They can be tricky:  https://leetcode.com/problems/product-of-the-last-k-numbers/ 1352. Product of the Last K Numbers Medium 73 6 Add to List Share Implement the class  ProductOfNumbers  that supports two methods: 1.  add(int num) Adds the number  num  to the back of the current list of numbers. 2.  getProduct(int k) Returns the product of the last  k  numbers in the current list. You can assume that always the current list has  at least   k  numbers. At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing. Example: Input ["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"] [[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]] Output [null,null,null,null,null,null,20,40,0,null,32] Explanation

How many Edit Distance problems are there? I guess a very high number.. This is the second most popular Dynamic Programming problem out there (guess the #1? Yeah, Fibonacci. By a mile). Here is another version of the Edit Distance problem:  https://leetcode.com/problems/one-edit-distance/ 161. One Edit Distance Medium 530 97 Add to List Share Given two strings  s  and  t , determine if they are both one edit distance apart. Note:   There are 3 possiblities to satisify one edit distance apart: Insert a character into  s  to get  t Delete a character from  s  to get  t Replace a character of  s  to get  t Example 1: Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s  to get  t. Example 2: Input: s = "cab", t = "ad" Output: false Explanation: We cannot get t from s by only one step. Example 3: Input: s = "1203", t = "1213" Output: true Explanation:

Three simple concepts in this problem, here is the problem:  https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/ 1343. Maximum Product of Splitted Binary Tree Medium 70 7 Add to List Share Given a binary tree  root . Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized. Since the answer may be too large, return it modulo 10^9 + 7. Example 1: Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10) Example 2: Input: root = [1,null,2,3,4,null,null,5,6] Output: 90 Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6) Example 3: Input: root = [2,3,9,10,7,8,6,5,4,11,1] Output: 1025 Example 4: Input: root = [1,1] Output: 1 Constraints: Each tree has at most  50000  nodes and at least  2  nodes. Each node's value is be