Another Casual Coder

I'm a big believer that you should do what you like to do, what you're passionate about.  One of my hobbies is LeetCode. I say as a hobby because that's what it really is: there is no expectation from my part that these problems will help me professionally (if one day they do, that's a bonus). I truly just do it because I enjoy - just as if you like playing video games, you should then just play. Just be happy :)  Today I got to my 450th solved problem (over a couple of years now). The problem was to "find the leaves on a binary tree, and keep removing them and finding new leaves":  https://leetcode.com/submissions/detail/271722558/ The solution is to literally just do that: find the leaves (DFS), remove them (that's why you need to pass the parent node along), and repeat until all the nodes are gone. On average the execution time will actually be NLogN since at every point you remove 1/2 the tree but you still need to traverse all nodes, hence N...

Problem is here:  https://leetcode.com/problems/queens-that-can-attack-the-king/ On an  8x8  chessboard, there can be multiple Black Queens and one White King. Given an array of integer coordinates  queens  that represents the positions of the Black Queens, and a pair of coordinates  king  that represent the position of the White King, return the coordinates of all the queens (in any order) that can attack the King. Example 1: Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0] Output: [[0,1],[1,0],[3,3]] Explanation:   The queen at [0,1] can attack the king cause they're in the same row. The queen at [1,0] can attack the king cause they're in the same column. The queen at [3,3] can attack the king cause they're in the same diagnal. The queen at [0,4] can't attack the king cause it's blocked by the queen at [0,1]. The queen at [4,0] can't attack the king cause it's blocked by the queen at [1,0]. The queen at [2,...

Problem is here:  https://leetcode.com/problems/triangle/ Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [ 2 ], [ 3 ,4], [6, 5 ,7], [4, 1 ,8,3] ] The minimum path sum from top to bottom is  11  (i.e.,  2  +  3  +  5  +  1  = 11). Note: Bonus point if you are able to do this using only  O ( n ) extra space, where  n  is the total number of rows in the triangle. Traditional DP problem: keep a track of the min sum for each position from [0..n-1]. You actually use 2*n space for previous  and current , swapping them along the way. Code is below. In 2020 it would be the 100th birthday for Richard Bellman, the inventor of Dynamic Programming - Happy BDay, Sir!!! ACC. public class Solution {     public int MinimumTotal(IList<IList<int>> trian...

Problem is here:  https://leetcode.com/problems/path-with-maximum-gold/ In a gold mine  grid  of size  m * n , each cell in this mine has an integer representing the amount of gold in that cell,  0  if it is empty. Return the maximum amount of gold you can collect under the conditions: Every time you are located in a cell you will collect all the gold in that cell. From your position you can walk one step to the left, right, up or down. You can't visit the same cell more than once. Never visit a cell with  0  gold. You can start and stop collecting gold from  any  position in the grid that has some gold. Example 1: Input: grid = [[0,6,0],[5,8,7],[0,9,0]] Output: 24 Explanation: [[0,6,0], [5,8,7], [0,9,0]] Path to get the maximum gold, 9 -> 8 -> 7. Example 2: Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] Output: 28 Explanation: [[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]] P...

Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are...

Medium-level problem:  https://leetcode.com/problems/two-sum-bsts/ Given two binary search trees, return  True  if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer  target . Example 1: Input: root1 = [2,1,4], root2 = [1,0,3], target = 5 Output: true Explanation: 2 and 3 sum up to 5. Example 2: Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18 Output: false Constraints: Each tree has at most  5000  nodes. -10^9 <= target, node.val <= 10^9 Likely the author is expecting an O(nlogn) solution, but there is a way to do in O(n) if you're willing to spare some extra space: Push the items from the first tree (non-recursively) into a Hashtable Go thru each item in the second tree looking for Target-Item in the Hashtable Runs in 120ms. Code is below, cheers, ACC. public class Solution {     public bool TwoSumBSTs(TreeNode root...

Problem is here:  https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ Given a binary tree, flatten it to a linked list in-place. For example, given the following tree: 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 The interesting aspect of this problem is that you cannot create a separate structure to accommodate the flatten list - rather, you're supposed to change the current Tree. In order to do that, what I did was the following: 1) Step one was to make a copy of the initial tree. This sub-problem looks relatively easy, but you should try it, it actually has some nuances worth checking 2) Once with the copy of the tree, you can do a pre-order traversal using the copy and then assign to the root tree appropriately It did the trick. Cheers, ACC. public class Solution {     public void Flatten(TreeNode root)     { ...