Category: Uncategorized
-
LeetCode 455: Assign Cookies
link If we cannot satisfy the least greedy kid with the smallest cookie, we cannot satisfy any other kid with that cookie. Time: , space: . Although does not improve worst case, to reduce waste, we can match more than one compatible (cookie, kid)-pairs at once. To improve space complexity we could trade heap for…
-
LeetCode 2384: Largest Palindromic Number
link For a digit, instances of it can be placed at the two ends of a palindrome. If there is one instance of the digit still left, it can be the center. In both cases, we should pick largest digit first. The palindrome cannot have leading zeros. We have a leading zero if pal_half‘s first…
-
LeetCode 871: Minimum Number of Refueling Stops
link Dynamic Programming The optimal refueling would look like a subsequence of (start, stations, target). For each station, we can find how far we can go with different number of refuelings. Then the minimum number of refuelings that gets us to the target is the answer. Time: , space: . Greedy We refuel only if…
-
LeetCode 134: Gas Station
link Time: , space: . For a gas station, the net (gas-cost) >= 0 means we can make it to the next station. Since sum does not depend on the order of the numbers being summed up (commutativity), this also holds for a sequence of gas stations. Therefore, the sum of the nets of a…
-
LeetCode 881: Boats to Save People
link Blind alleys What works The best pairing for the heaviest person is the lightest person. If combining the weight of the lightest person does not work, the heaviest person must ride alone. So, we sort the weights and on each iteration try pairing the heaviest with the lightest. Time: , space: .
-
LeetCode 55: Jump Game
link As long as all indices (possibly except last index) have positive jumps, we can reach the end. Therefore, only way we may fail to reach the end is: Like the the case below: We keep improving the maximum allowed index. If current index is beyond our reach, we cannot reach the last index. Time:…
-
LeetCode 81: Search in Rotated Sorted Array II
link Time: , space: . If all numbers were distinct, we could find which side of pivot is on by comparing with as below. Here, with duplicates allowed, we reduce the problem to the all-distinct case by making sure .
unreasonably effective 