Problems
November 20, 2022
Path with maximum probability
We can use Dijkstra's algorithm to find the shortest path from the start node to the end node. We will keep track of the probability of the shortest path from the start node to the current node. Then...
ReadNovember 20, 2022
Reverse prefix of word
We will iterate through the word and check if the current character is equal to the first character of the prefix. If it is, we will reverse the prefix and return the word. Time complexity:...
ReadNovember 20, 2022
Shopping offers
We can use DFS with memoization to solve this problem. We will keep track of the current state of the shopping list. Then we will iterate over each offer and we will check if the offer is valid. If...
ReadNovember 20, 2022
Widest vertical area between two points containing no points
We sort the points by x-coordinate, and find the maximum distance between two consecutive points.
Time complexity: O(nlogn)
Space complexity: O(n)
November 19, 2022
Binary subarrays with sum
We can count the occurance of all the prefix sums. Then we will iterate through the prefix sums and check if the prefix sum minus the goal is in the hashmap. If yes, we will add the number of...
ReadNovember 19, 2022
Erect the fence
The problem is asking us to find the convex hull given a set of 2D points. Monotone Chain algorithm: Sort the points by x. (moving from left to right) Initialize a stack with the first 2 points....
ReadNovember 19, 2022
Maximum product after k increments
We will use a heap to keep track of the minimum element in the array. Then we will iterate k times and we will pop the minimum element from the heap and add 1 to it. We will push the new element back...
ReadNovember 19, 2022
Number of ways to split array
We will keep track of the left sum and right sum of the array. Then we iterate over each element until the last element, and we will check if the left sum is equal to the right sum. If yes, we will...
ReadNovember 18, 2022
First letter to appear twice
We will use a hashset to keep track of the letters we have seen. If we see a letter that is already in the hashset, we return it. Otherwise we add it to the hashset. Time complexity:...
ReadNovember 18, 2022
Frog position after t seconds
We will create a adjacency list to represent the graph. We will then use a DFS to traverse the graph. We will keep track of the number of children each node has. If the node has no children, we will...
Read