Problems
November 16, 2022
Construct binary search tree from preorder traversal
As preorder traversal is given, we know the first element will be the root. We will create a function witg a bound the maximum number it will handle. The left recursion will take the elements smaller...
ReadNovember 16, 2022
Count days spent together
We will use a helper function to get the number of days from the beginning of the year to the given date. Then take the maximum of arrival date and minimum of departure date and subtract the minimum...
ReadNovember 16, 2022
Insert into a binary search tree
We will use DFS for inserting. We recursively insert the left and right subtrees and then return the root. If the root is null, we return the new node. If the root is greater than the value, we...
ReadNovember 16, 2022
Making file names unique
We will use a hashmap to store the count of each file name. We will iterate over all the file names and if the file name is not present in the hashmap, we will add it to the result. If the file name...
ReadNovember 16, 2022
Trim a binary search tree
We will use DFS for trimming. We recursively trim the left and right subtrees and then return the root. If the root is less than low, we return the right subtree, and if the root is...
November 16, 2022
Path in zigzag labelled binary tree
We will use DFS for finding the path. We recursively find the path in the left and right subtrees and then return the root. If the root is in the set, we return the left and right subtrees, and if...
ReadNovember 15, 2022
Dungeon game
We will solve the problem recursively and then memoize the result to avoid duplicate computation. For base case, if the knight is at the bottom right corner, then the minimum health required is 1. If...
ReadNovember 15, 2022
Make two arrays equal by reversing subarrays
We can sort both arrays and compare them. If they are equal, then we can make the two arrays equal by reversing subarrays.
Time complexity: O(nlog(n))
Space complexity:...
November 15, 2022
Maximum width of binary tree
We will use BFS to find the maximum width of the tree.
Time complexity: O(n)
Space complexity: O(n)
November 15, 2022
Most frequent subtree sum
First we will use DFS to find all the subtree sum and then use a hash map to store the frequency of each subtree sum. Then we can find the most frequent subtree sum. Time complexity:...
Read