-
LeetCode 994: Rotting Oranges
link We let rotting wavefronts emanate from all rotten oranges in each iteration of BFS. As soon as fresh orange count drops to zero we are done. Time: , space: .
-
LeetCode 42: Trapping Rain Water
link A bar can hold some water atop if there are left and right supports for it. So, we can compute water on top of each bar and sum up. Time: , space: . We could pre-compute left and right support for each index. Time: , space: . With two pointers moving from two ends,…
-
Distributed Cache
Memcache A global, in-memory hash-table distributed across servers. Key and value are strings, item has TTL on top of LRU eviction. Memcache@scale
-
LeetCode 1029: Two City Scheduling
link Brute force Try flying each person to city A and city B and take the minimum cost. Time: , space: . Greedy For a cost pair , when we decide to fly a person to city A, we are also deciding to not fly that person to city B. We have to optimize both…
-
LeetCode 22: Generate Parentheses
link Valid parentheses have two criteria: Recursive Time: , space: .
-
LeetCode 17: Letter Combinations of a Phone Number
link Recursive Letter combinations of “23” is the cartesian product of corresponding letter sets: {“a”, “b”, “c”} and {“d”, “e”, “f”}. Note, there can be at most four different letters for a digit. Time: , space: . Iterative For each possible letter for a new digit, we can append it to each of the earlier…
-
LeetCode 46: Permutations
link Recursive Time: , space: . Iterative For a new element , for each earlier permutations, we can insert in different positions to get more permutations. Time: , space: .
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 