unreasonably effective

link Profit is (sell-buy). For each possible buy, we find the best sell (max day’s price) in the future. Time: , space: . Going through the days in sequence, we keep track of the best_buy; therefore, the minimum price seen so far. Everyday we consider selling and to compute the max_profit for that day we…

link Discard as little as possible. Time: , space:

link Time: , space: .

link A swap cannot increase numbers like below: We need an increasing pair. Those two numbers will be candidate for swap. We can improve the right. Given the improved right, now we can also improve the left. Time: , space: .

link Time: , space: . Observations Or, more concisely:

link Observations Time: , space: .

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…

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…