## Posts

Showing posts from 2019

### Jump Game 3, BFS Approach

Standard problem for a BFS:  https://leetcode.com/problems/jump-game-iii/ 1306. Jump Game III Medium 60 0 Add to List Share Given an array of non-negative integers  arr , you are initially positioned at  start  index of the array. When you are at index  i , you can jump to  i + arr[i]  or  i - arr[i] , check if you can reach to  any  index with value 0. Notice that you can not jump outside of the array at any time. Example 1: Input: arr = [4,2,3,0,3,1,2], start = 5 Output: true Explanation: All possible ways to reach at index 3 with value 0 are: index 5 -> index 4 -> index 1 -> index 3 index 5 -> index 6 -> index 4 -> index 1 -> index 3 Example 2: Input: arr = [4,2,3,0,3,1,2], start = 0 Output: true Explanation: One possible way to reach at index 3 with value 0 is: index 0 -> index 4 -> index 1 -> index 3 Example 3: Input: arr = [3,0,2,1,2], start = 2 Output: false Explanation: There is no way to reach at index 1 with

### Designing Tic-Tac-Toe in Constant Time

The design of a tic-tac-toe is one of the most popular interview questions. It can be done in constant time and linear space. Here is the problem:  https://leetcode.com/problems/design-tic-tac-toe/ 348. Design Tic-Tac-Toe Medium 560 39 Add to List Share Design a Tic-tac-toe game that is played between two players on a  n  x  n  grid. You may assume the following rules: A move is guaranteed to be valid and is placed on an empty block. Once a winning condition is reached, no more moves is allowed. A player who succeeds in placing  n  of their marks in a horizontal, vertical, or diagonal row wins the game. Example: Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board. TicTacToe toe = new TicTacToe(3); toe.move(0, 0, 1); -> Returns 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | toe.move(0, 2, 2); -> Returns 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | |

### Sliding Window Maximum - 500th problem solved

There is literally no practical benefit for me in solving algo problems. None. Just a hobby that I've been enjoying since I wrote my first algorithm to do a "summation of few numbers". Felt like magic. Still does. This is my 500th LeetCode problem solved:  https://leetcode.com/problems/sliding-window-maximum/solution/ 239. Sliding Window Maximum Hard 2370 139 Add to List Share Given an array  nums , there is a sliding window of size  k  which is moving from the very left of the array to the very right. You can only see the  k  numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window. Example: Input: nums = [1,3,-1,-3,5,3,6,7] , and k = 3 Output: [3,3,5,5,6,7] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5

### Ultimate Serialization and Deserialization of an N-ary tree in C#

Problem is here:  https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/ 428. Serialize and Deserialize N-ary Tree Hard 289 13 Favorite Share Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure. For example, you may serialize the following  3-ary  tree as  [1 [3[5 6] 2 4]] . Note that this is just an example, you do not necessarily need to follow this format. Or you can follo

### Binary Tree Longest Consecutive Sequence: Post-Order Traversal

Problem is here:  https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/ 298. Binary Tree Longest Consecutive Sequence Medium 394 100 Favorite Share Given a binary tree, find the length of the longest consecutive sequence path. The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse). Example 1: Input: 1 \ 3 / \ 2 4 \ 5 Output: 3 Explanation: Longest consecutive sequence path is 3-4-5 , so return 3 . Example 2: Input: 2 \ 3 / 2 / 1 Output: 2 Explanation: Longest consecutive sequence path is 2-3 , not 3-2-1 , so return 2 . Best option is to perform a post-order tree traversal : Call for the left node Call for the right node Then calculate the value of the current node by checking whether the left AND the right are pot

### In-order Successor in BST

Problem is here:  https://leetcode.com/problems/inorder-successor-in-bst/ 285. Inorder Successor in BST Medium 878 55 Favorite Share Given a binary search tree and a node in it, find the in-order successor of that node in the BST. The successor of a node  p  is the node with the smallest key greater than  p.val . Example 1: Input: root = [2,1,3] , p = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type. Example 2: Input: root = [5,3,6,2,4,null,null,1] , p = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null . Note: If the given node has no in-order successor in the tree, return  null . It's guaranteed that the values of the tree are unique. As the problem statement implies, you'll be likely dealing with an InOrder traversal technique (to recap: Inorder => left, current, right). Throughout the traversal, keep track of a b

### A Message

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace _2019 {     class Program     {         static void Main(string[] args)         {             Console.WriteLine(F("H\$--.a%\$ 3a'3(\$/%2ma 3\"\$-.a(2a./a7 \" 5(./a4/5(-a\$ 3-8a /4 38oa f--a#\$a538(/&a,8a#\$25a5.a#\$\".,\$a a13.'\$22(./ -a243'\$3ma#45a\") /\"\$2a 3\$a(5a6(--a/.5a6.3*oa a6 /5a5.a6(2)a8.4a --a a7\$38a) 118a).-(% 82ma /%a a534-8a).1\$a5) 5a8.43asqpxa6 2a a&3\$ 5a8\$ 3ma /%a('a(5a6 2/f5ma%./f5a6.338masqsqa6(--a#\$a#\$55\$3oa a -2.a6 /5a5.a2 8a5) 5a f,a241\$3a5) /*'4-a'.3a5)\$a\".,1 /8a5) 5a a6.3*a'.3ai (\"3.2.'5`hma,8a'3(\$/%2a /%a\".--\$ &4\$2ai --a.'a5)\$,ma5)\$8a-(7\$a(/a,8a)\$ 35hma,8a' ,(-8ai\$7\$385)(/&a5.a,\$ha /%a,8a,\$/5.3a /%a13.5\$\"5.3{a .%oa 'a8.4f7\$a\".,\$a5)(2a' 3a8.4a,(&)5a6 /5a5.a\")\$\"*a5)\$a3\$25a.'a5)(2a#-.&ma(

### On the Deserialization of a Binary Tree

Problem is here:  https://leetcode.com/problems/construct-binary-tree-from-string/ 536. Construct Binary Tree from String Medium 315 79 Favorite Share You need to construct a binary tree from a string consisting of parenthesis and integers. The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure. You always start to construct the  left  child node of the parent first if it exists. Example: Input: "4(2(3)(1))(6(5))" Output: return the tree root node representing the following tree: 4 / \ 2 6 / \ / 3 1 5 Note: There will only be  '(' ,  ')' ,  '-'  and  '0'  ~  '9'  in the input string. An empty tree is represented by  ""  instead of  "()" . It deals with the deserializat