## Posts

Showing posts from January, 2020

### Integer to English Words (Hard) Here is a hard problem to convert a number to English words:  https://leetcode.com/problems/integer-to-english-words/ 273. Integer to English Words Hard 752 2138 Add to List Share Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2 31  - 1. Example 1: Input: 123 Output: "One Hundred Twenty Three" Example 2: Input: 12345 Output: "Twelve Thousand Three Hundred Forty Five" Example 3: Input: 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" Example 4: Input: 1234567891 Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One" Accepted 138,107 Submissions 537,502 The problem is laborious (in terms of effort to write a lot of boring code) but actually not that hard if you use one technique: create a helper function that converts a number with up to t

### The powerful bucket sort This problem exemplifies one of the best methods to sort out there - bucket sort. Here is the problem:  https://leetcode.com/problems/sort-the-matrix-diagonally/ 1329. Sort the Matrix Diagonally Medium 19 12 Add to List Share Given a  m * n  matrix  mat  of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array. Example 1: Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]] Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]] Constraints: m == mat.length n == mat[i].length 1 <= m, n <= 100 1 <= mat[i][j] <= 100 The highlighted line above is the key to solving this problem quickly. The approach first is to create a helper function to sort the contents in the array from (row, col) all the way down to (row+k, col+k) where k increments from one until row+k and col+k are within the limits of the matrix. Since the number allowed in the matrix are in the range 1..100, you can use bucket sort: keep track of t

### Slight variation of a Priority Queue This problem exemplifies the power of a Priority Queue, as well as the advantages of having one's own implementation which you can then tweak as needed. Here it is:  https://leetcode.com/problems/rank-transform-of-an-array/ 1331. Rank Transform of an Array Easy 16 0 Add to List Share Given an array of integers  arr , replace each element with its rank. The rank represents how large the element is. The rank has the following rules: Rank is an integer starting from 1. The larger the element, the larger the rank. If two elements are equal, their rank must be the same. Rank should be as small as possible. Example 1: Input: arr = [40,10,20,30] Output: [4,1,2,3] Explanation : 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest. Example 2: Input: arr = [100,100,100] Output: [1,1,1] Explanation : Same elements share the same rank. Example 3: Input: arr = [37,12,28,9,100,56,80,5,12] Output: [5,3,4,2,8,6,7,1,

### Longest Turbulent Subarray - Fibonacci's Approach Problem is here:  https://leetcode.com/problems/longest-turbulent-subarray/ 978. Longest Turbulent Subarray Medium 194 64 Add to List Share A subarray  A[i], A[i+1], ..., A[j]  of  A  is said to be  turbulent  if and only if: For  i <= k < j ,  A[k] > A[k+1]  when  k  is odd, and  A[k] < A[k+1]  when  k  is even; OR , for  i <= k < j ,  A[k] > A[k+1]  when  k  is even, and  A[k] < A[k+1]  when  k  is odd. That is, the subarray is turbulent if the comparison sign flips between each adjacent pair of elements in the subarray. Return the  length  of a maximum size turbulent subarray of A. Example 1: Input: [9,4,2,10,7,8,8,1,9] Output: 5 Explanation: (A > A < A > A < A) Example 2: Input: [4,8,12,16] Output: 2 Example 3: Input:  Output: 1 Note: 1 <= A.length <= 40000 0 <= A[i] <= 10^9 Use same approach used to calculate the Nth Fibonacci's number:keep track of the pre

### Find Elements in a Contaminated Binary Tree - Medium Problem This problem demonstrates clearly that both in Mathematics as well as in Computer Science/Algorithms, one of the key points to solving a problem correctly is understanding the problem correctly . Here we go  https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/ Given a binary tree with the following rules: root.val == 0 If  treeNode.val == x  and  treeNode.left != null , then  treeNode.left.val == 2 * x + 1 If  treeNode.val == x  and  treeNode.right != null , then  treeNode.right.val == 2 * x + 2 Now the binary tree is contaminated, which means all  treeNode.val  have been changed to  -1 . You need to first recover the binary tree and then implement the  FindElements  class: FindElements(TreeNode* root)  Initializes the object with a contamined binary tree, you need to recover it first. bool find(int target)  Return if the  target  value exists in the recovered binary tree. Example 1: Input ["FindElements","find","fi

### Delete Leaves With a Given Value Problem is here  https://leetcode.com/problems/delete-leaves-with-a-given-value/ 1325. Delete Leaves With a Given Value Medium 49 0 Add to List Share Given a binary tree  root  and an integer  target , delete all the  leaf nodes  with value  target . Note that once you delete a leaf node with value  target ,  if it's parent node becomes a leaf node and has the value  target , it should also be deleted (you need to continue doing that until you can't). Example 1: Input: root = [1,2,3,2,null,2,4], target = 2 Output: [1,null,3,null,4] Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). After removing, new nodes become leaf nodes with value (target = 2) (Picture in center). Example 2: Input: root = [1,3,3,3,2], target = 3 Output: [1,3,null,null,2] Example 3: Input: root = [1,2,null,2,null,2], target = 2 Output:  Explanation: Leaf nodes in green with value (target = 2) are removed at each step. Example

### Sum of Nodes with Even-Valued Grandparent Although labeled as Medium, the problem is actually quite easy:  https://leetcode.com/problems/sum-of-nodes-with-even-valued-grandparent/ 1315. Sum of Nodes with Even-Valued Grandparent Medium 19 1 Add to List Share Given a binary tree, return the sum of values of nodes with even-valued grandparent.  (A  grandparent  of a node is the parent of its parent, if it exists.) If there are no nodes with an even-valued grandparent, return  0 . Example 1: Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] Output: 18 Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents. Constraints: The number of nodes in the tree is between  1  and  10^4 . The value of nodes is between  1  and  100 . Accepted 2,014 Submissions 2,439 Approach:  - DFS PreOrder  - Carry over parent value and grandparent value  - Simple base case to add to the sum  - Induction changing the par