Posts

On the Collatz Conjecture II

I've written about the Collatz Conjecture before, right here:  https://anothercasualcoder.blogspot.com/2019/05/on-collatz-conjecture.html Coincidentally, this LC problem talks about it. Here it is:  https://leetcode.com/problems/sort-integers-by-the-power-value/ 1387. Sort Integers by The Power Value Medium 16 0 Add to List Share The power of an integer  x  is defined as the number of steps needed to transform  x  into  1  using the following steps: if  x  is even then  x = x / 2 if  x  is odd then  x = 3 * x + 1 For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1). Given three integers  lo ,  hi  and  k . The task is to sort all integers in the interval  [lo, hi]  by the power value in  ascending order , if two or more integers have  the same  power value so...

Create Balanced BST

Problem is here:  https://leetcode.com/problems/balance-a-binary-search-tree/ 1382. Balance a Binary Search Tree Medium 16 4 Add to List Share Given a binary search tree, return a  balanced  binary search tree with the same node values. A binary search tree is  balanced  if and only if the depth of the two subtrees of every node never differ by more than 1. If there is more than one answer, return any of them. Example 1: Input: root = [1,null,2,null,3,null,4,null,null] Output: [2,1,3,null,null,null,4] Explanation: This is not the only correct answer, [3,1,4,null,2,null,null] is also correct. Constraints: The number of nodes in the tree is between  1  and  10^4 . The tree nodes will have distinct values between  1  and  10^5 . There is a standard way to create a balanced BST from a sorted array, which is this: 1) Get the Middle of the array and make it root. 2) Recursively ...

Dijkstra's Variation

Usually  Dijkstra's Algorithm is used to find weighted {min, max} paths in a graph. It does have a well-structured format. Sometimes, though, a slight variation is needed. Here is a problem to exemplify it:  https://leetcode.com/problems/path-with-maximum-minimum-value/ 1102. Path With Maximum Minimum Value Medium 300 35 Add to List Share Given a matrix of integers  A  with  R  rows and  C  columns, find the  maximum  score of a path starting at  [0,0]  and ending at  [R-1,C-1] . The  score  of a path is the  minimum  value in that path.  For example, the value of the path 8 →  4 →  5 →  9 is 4. A  path  moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south). Example 1: Input: [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path wi...

Your programming language is more powerful than you think

Your programming language is more powerful than you think. Case in point:  https://leetcode.com/problems/max-stack/ 716. Max Stack Easy 600 115 Add to List Share Design a max stack that supports push, pop, top, peekMax and popMax. push(x) -- Push element x onto stack. pop() -- Remove the element on top of the stack and return it. top() -- Get the element on the top. peekMax() -- Retrieve the maximum element in the stack. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one. Example 1: MaxStack stack = new MaxStack(); stack.push(5); stack.push(1); stack.push(5); stack.top(); -> 5 stack.popMax(); -> 5 stack.top(); -> 1 stack.peekMax(); -> 5 stack.pop(); -> 1 stack.top(); -> 5 Note: -1e7 <= x <= 1e7 Number of operations won't exceed 10000. The last four operations won't be called when stack is empty. Usually a good alternative ...

Hints in the problem description can really simplify your solution

Take a look at this particular problem (medium). If you read it carefully, the solution might be easier than an "easy" problem: https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/ 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree Medium 7 4 Add to List Share Given two binary trees  original  and  cloned  and given a reference to a node  target  in the original tree. The  cloned  tree is a  copy of  the  original  tree. Return  a reference to the same node  in the  cloned  tree. Note  that you are  not allowed  to change any of the two trees or the  target  node and the answer  must be  a reference to a node in the  cloned  tree. Follow up:  Solve the problem if repeated values on the tree are allowed. Example 1: Input: tree = [7,4,3,null,null,6,19], target =...

Memoization II

I wrote about memoization many years ago. Memoization is a glorified caching. Here is when it can come handy:  https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/ 1372. Longest ZigZag Path in a Binary Tree Medium 54 1 Add to List Share Given a binary tree  root , a ZigZag path for a binary tree is defined as follow: Choose  any  node in the binary tree and a direction (right or left). If the current direction is right then move to the right child of the current node otherwise move to the left child. Change the direction from right to left or right to left. Repeat the second and third step until you can't move in the tree. Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0). Return the longest  ZigZag  path contained in that tree. Example 1: Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1] Output: 3 Explanation: Longest ZigZag p...