Category: foundational_interview
-
LeetCode 213: House Robber II
link Dynamic Programming Sub-problem Say Rob(i) is the maximum money achievable by robbing the houses in nums[0…i]. Then: . Order The directed graph is cyclic. To break the cycle, we do two passes. First pass robs first house and thus skips the last house. Second pass skips first house. We take the maximum of these…
-
LeetCode 542: 01 Matrix
link Dynamic programming For a one-cell (i, j) we can reach the nearest zero-cell via one of its four neighbors. So, if the four neighbors of the cell have already been solved, we can solve (i, j). This suggests DP. Sub-problem Order The directed graph has cycles between neighbors. We can process black arrows in…
-
LeetCode 338: Counting Bits
link Inspect binary representation Count 1’s in binary representation for each index. For a number , count_ones take time. So, the time taken to count ones for all the numbers is the sum: or time is . We use Sterling’s approximation: . So, . Time: , extra space (disregarding output): . Dynamic programming On every…
-
LeetCode 416: Partition Equal Subset Sum
link Assigning the positive numbers in two equal-sum subsets is same as creating one set having sum equal to half of the total sum. We can use Dynamic Programming. This is like coin-change except a number cannot be reused. Sub-problem Let solutions[ (i, s) ] represent the sub-problem of creating a subset with target sum…
-
LeetCode 1137: N-th Tribonacci Number
link We can use Dynamic Programming. Sub-problem solutions[i] = solutions[i-1] + solutions[i-2] + solutions[i-3] Trivial sub-problems: solutions[0], solutions[1], and solutions[2] Order Since solutions[i] only depends on solutions[j] where j < i, we can process the sub-problems in increasing order of i and that would be a topologically sorted order.
-
LeetCode 473: Matchsticks to Square
link Adding up the matchsticks gives the square’s and the square’s expected side length is . Now, using all the matchsticks exactly once, we need to build the four sides–each side must have the expected length. Backtracking From a side’s point of view We try making one side at a time using all combinations of…
-
LeetCode 37: Sudoku Solver
link We collect all empty cells in a list and try filling them up using only the currently available digits for that cell. As a pre-processing step, we also populate (and later use): A digit is available for the empty cell (row, col) only if none of the above three contains the digit. If there…
-
LeetCode 465: Optimal Account Balancing
link We can summarize all transactions as balances per person. In the end, there might be positive balances and negative balances, but they must sum up to 0. Blind alleys What works Try matching each positive balance with each negative balance making sure a transaction does not change a positive balance to negative or a…
-
LeetCode 401: Binary Watch
link We can generate hours and minutes separately and take their Cartesian product to create valid times. For a given number of turned on hour (or minute) bits, we generate subsets of hour (or minute) bits. Time: , space: .
-
LeetCode 2850: Minimum Moves to Spread Stones Over Grid
link The problem restricts placing one stone per move, otherwise it would have been harder. The problem here is to find the minimum total cost of assigning every empty cell to one extra stone. The cost of one such assignment is the Manhattan distance between the empty cell and the stone’s cell. We construct a…
unreasonably effective 