Problems
August 6, 2022
Letter combinations of a phone number
We will create a hashmap to map all the digits to the characters. The we will run backtracking to get all possible combinations of those characters and return the result. Time Complexity:...
ReadAugust 6, 2022
Merge k sorted lists
We can merge 2 sorted list with O(n) time complexity. Now we can go through the lists, and merge it one by one, this will be a O(n^2) operation. But if we merge every 2 list...
August 6, 2022
Poor pigs
With 2 pigs, poison killing in 15 minutes, and having 60 minutes, we can find the poison in up to 25 buckets in the following way. Arrange the buckets in a 5×5 square- Now use one pig to find the...
ReadAugust 6, 2022
Reverse nodes in k group
We will create a helper funtion to get the kths item of the list. Then as we go through the whole list, we will take kth item, reverse it in place and move forward till the end of the ;list. Time...
ReadAugust 6, 2022
Serialize and deserialize binary tree
For serialize the tree, we will traverse the tree in preorder and whenever we hit a null node, we put a # character there. Then we join each character with a comma delimeter and return...
August 6, 2022
Validate binary search tree
We will run a DFS, and each iteration we will compare the value of the node with a left and right value, which we will pass along each iteration. For root, this values will be negative and positive...
ReadAugust 5, 2022
Coin change 2
We will first solve the problem with brute force using recursion. Then we use memoization to reduce it's complexity.
Time Complexity: O(n*a), n is the number of coins, a is the amount...
August 5, 2022
Combination sum II
We will run a DFS for the decision tree and use backtracking if we failed to find a result. As we are bit allowed to use the same items twice, we will keep track of the previous item, and if it is...
ReadAugust 5, 2022
Combination sum IV
This is very similar to coin change 2. But when you take one item from the allowed list, rather start it from the same index like coin change, you should start it from the beginning of the list....
ReadAugust 5, 2022
Combination sum
Basically, we have 2 ways to built the decision tree, either take the number or skip it. We are going to use backtracking to calculate the problem.
Time Complexity: O(2^n)
Space...