Problems
July 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 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
Network delay time
We will use Dijkstra's shortest path algorithm to solve this problem. First we will create an adjacency list from the edge list, where the key will be the source node and value will be a tuple...
ReadJuly 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 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 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
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 24, 2022
Implement queue using stacks
We will have 2 stack, one for input, one for output. Whenever we push anything, we push it to the input stack, then pop every element from input stack and push it back to output stack. Every other...
ReadJuly 24, 2022
Longest substring without repeating characters
We will use a set to keep track of repeating characters. We will have 2 pointers, we will move our right pointer, check if the character as right pointer is already exist in the set, if exists, then...
Read