Problems
December 29, 2022
Leftmost column with at least a one
We do a binary search on each of the $m$ rows, finding the earliest 1 on each. On this binary search, we only search the first minCol columns, where minCol is the earliest column where...
December 28, 2022
Maximum tastiness of candy basket
We will sort the prices of the candies. Then we run a binary search in the range 0 to the maximum difference between the candies. The check function iterates over the array prices and checks if the...
ReadDecember 28, 2022
Minimum path cost in a grid
We will use recursion with memoization to solve this problem. The function helper takes the current position (r, c) and the current cost cost. If the current...
December 28, 2022
Count number of ways to place houses
One side of the road has no effect on the other side of the road, so we can put house in both side independently. For one side, we could have number of ways as fibonacci sequence. We we calculate the...
ReadDecember 28, 2022
Design a leaderboard
We will use a hashmap to store the score of each player. We will store the score of each player and we can look up in constant time.
Time complexity: O(1) for addScore...
December 28, 2022
Minimum penalty for a shop
We will count the number of penaly and then iterate over the customers, canculate the minimum penalty for each customer and add it to the total penalty.
Time complexity: O(n)
Space...
December 28, 2022
Minimum increment to make array unique
We will sort the array and iterate over the array. If the current element is smaller than the previous element, we will increment the current element to the previous element plus one. Time...
ReadDecember 28, 2022
Minimum remove to make valid parentheses
We will use a stack to store the index of the open parentheses. If we see a close parentheses, we will pop the stack. If the stack is empty, we will mark the close parentheses as invalid. After we...
ReadDecember 27, 2022
Maximum bags with full capacity of rocks
We will sort the rocks by weight and then iterate over them. If the current rock fits in the bag, we will add it to the bag. Otherwise, we will create a new bag. Time complexity:...
ReadDecember 27, 2022
First day where you have been in all the rooms
The idea is that we need to go back a lot of times. Define by dp[i] is number of days to reach cell i. We can only reach it from the cell i-1, so we need at least dp[i-1] steps. Then it will lead us...
Read