-
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…
-
LeetCode 75: Sort Colors
link We count 0’s, 1’s, and 2’s. Then fill up nums starting with 0’s, then 1’s followed by 2’s. Time: , space: . We could sort an array around a pivot in one pass. We shall use pivot == 1 for this problem. We shall maintain nums like below: Initially, the entire nums consists of…
-
LeetCode 733: Flood Fill
link If source color and target color are the same, nothing to do. Otherwise, we remember the source color, color the cell and its four neighbors. A cell is filled at most once. Time: , space: .
-
LeetCode 93: Restore IP Addresses
link With the 3 dots inserted, the length of a valid ip address is len(s)+3. We create different possible four-parts via backtracking and include the valid ones. Time: , space: .
-
LeetCode 79: Word Search
link We try finding the word one character at a time starting from every cell avoiding already visited cells. Say . Time: , space: . Follow up: Could you use search pruning to make your solution faster with a larger board? We start searching with a word character that appears the least in the board, in that…
-
LeetCode 51: N-Queens
link We place queens one row at a time keeping track of columns, main diagonals, and sub-diagonals under attack. For each row we place the queen on a column if (row, column) is not already under attack — horizontally, vertically, or diagonally. For some row, if we cannot find a non-attacked column, we backtrack. Main…
-
LeetCode 125: Valid Palindrome
link Try matching lowercase left and right skipping over non-alphanumeric characters. Time: , space: .
-
LeetCode 19: Remove Nth Node From End of List
link As long as we know the previous and the next nodes of the to-be-deleted node, we can update the pointers to delete the node. Say there are total nodes in the list. Say the -th node from the end is the -th node from the head. Then, and . From the head, if we…