Problems
September 6, 2022
Sort an array
We will use divide and conquar to solve this sorting porblem. We will be using classic merge sort.
Time Complexity: O(nlog(n))
Space Complexity: O(nlog(n))
September 6, 2022
Replace words
We will use a prefix tree or trie with our dictionary. Then for each word in the sentence, we will look for the root of the word in the trie, if we found something, we will replace it with our root,...
ReadSeptember 6, 2022
Seat reservation manager
We will create a min heap with the capacity of the seat manager. Then when someone reserve a seat, we will pop it from our min heap, and when someone unreserve a seat, we will push back the value to...
ReadSeptember 6, 2022
Binary tree pruning
We will do a recursive DFS and check there the leaf node is 0 if 1, if it's 0, we remove it. Finally return the tree root.
Time Complexity: O(n)
Space Complexity: O(n)
September 5, 2022
Battleships in a board
We will run DFS to explore all the values after we found one X and mark that as visited and count the number of battleship by 1. After traverse the whole board, we will return the count...
September 5, 2022
Single number III
We will be using the XOR trick i.e n^n=0. During first traversal we will get the XOR of the required two numbers, then we will get the least significant bit of the XOR operation. This...
September 5, 2022
Path sum II
We will use DFS along with backtracking to get the paths of every root to leaf path that adds upto the target.
Time Complexity: O(n)
Space Complexity: O(n), for...
September 5, 2022
Basic calculator III
We will take a stack. Initially our operation and operand will be 0 and + append each character to the stack. If the character is numeric, until we reach an operand we will calculate the...
September 5, 2022
House robber III
We will traverse the tree in DFS and take both with and without root result. Then we calculate the max from both of them and return the result.
Time Complexity: O(n)
Space...
September 5, 2022
Linked list cycle II
We can use Floyd's cycle detection algorithm to find the position. We will create a fast and slow pointer, fast pointer is twice as fast as the slow pointer. If the two pointer doesn't meet, that...
Read