Problems
July 26, 2022
Verifying an alien dictionary
This is actually a subproblem of alien dictionary. First we will create a function for checking lexical order of 2 words based on the input order. We will go through each characters of the words, and...
ReadJuly 26, 2022
Lowest common ancestor of a binary tree
We check if p or q are equal to root, then we return root as we are guranteed to have a common ansestor. If not then we recursively call the function for both left and right subtree. If we found...
ReadJuly 26, 2022
Alien dictionary
We will first create an adjacency list from our input array. If 2 array has a different first charcter, then word1[0] should be arreared before word2[0]. When the grph is already created, we can then...
ReadJuly 26, 2022
Cheapest flights within k stops
We will solve the problem using Bellman-Ford algorithm. Initially we will assign infinity prices to all nodes except the source nodes price will be 0. We will basically run the BFS for k+1 steps as...
ReadJuly 26, 2022
Count good nodes in binary tree
We will traverse the tree with DFS and in the process we check if the value of the node is greater than or equals to it's child nodes. If wes, then we count it. After the traverse is done, we return...
ReadJuly 25, 2022
Trapping rain water
We will iterate over the whole list, and also check the left and right side for the highest value, then substruct the value itself from the highest value, ans add it to a running sum. Then we return...
ReadJuly 25, 2022
Find first and last position of element in sorted array
We will first do a regular binary search to get the position of the target. Then we expand both ways to get the left and right position of the target and return that. If we can't find the target we...
ReadJuly 25, 2022
Brust balloons
Fist we will add 1 in either side of the input list to tackle terminal edges. We will create a decision tree, the base case will be if we brust the element last, then the coin would be the balloon...
ReadJuly 24, 2022
Permutations
We will solve it recursively using backtracking. If there is only one element in the list, permutations of this will return the same list. This will be our base case. If it has 2 elements, we remove...
ReadJuly 24, 2022
Search a 2d matrix
We can just consider the matrix as a linear sorted array. Then if we need an element number i in our flattened list, we can get it by matrix[i//col][i%col]. Then we can do a regular binary search on...
Read