unreasonably effective

link We can keep a map: {number -> count}. To find two numbers that sum up to value, we can iterate through the map. For x, (value – x) must be in the map. If x and (value – x) are equal, then the count of x must be at least 2. Say, there are…

link We keep track of the window sum. If window has too many numbers we pop the oldest, updating sum. Operation Time Space __init__ next

link Stack of (num, curr_max) We can keep current max with the element. Say len(stack) = . Operation Time Space __init__ push pop top peekMax popMax Above, in the worst-case, popMax() needs to sift through the entire stack. To make finding max faster, we can use max heap. LinkedList and Max-Heap We keep two stacks:…

link List of LinkedLists We can use a fixed length list of LinkedList‘s. A key is put into the LinkedList or bucket at index hash(key). Say len(buckets) = and there are keys. The cost of operations depend on the load-factor, . And the load-factor depends on how evenly the hash distributes the keys across different…

link There can be multiple instances of both word1 and word2. We need to find the shortest distance among the possible pairs. List and sliding window We do not maintain any auxiliary data structure. Using sliding window [begin_word, end_word], where begin_word in {word1, word2} and end_word in {word1, word2} \ {begin_word}, we can find the…

link Set We can keep a set of the actual numbers contained within ranges. Sorted list of ranges We maintain a list of disjoint ranges sorted by left. Say at the time of operations, there are disjoint ranges. Total space is . Operation Time Space __init__ addRange queryRange removeRange Since we have a sorted list…

link Top of the stack also keeps current minimum. Operation Time Space __init__ push pop top getMin Instead of keeping min per value, we can use a separate stack for mins. This way we need space for unique mins only.

If we have a set of values: , in a sequence of getRandom() calls, each of the six permutations of must appear roughly equal number of times. We assume random.randint(lo, hi) takes time. List We can keep a list of values and pick an index at random. Say there are values. Total space is .…

link Dict and LinkedList If we did not have to evict keys, we could just keep a {key -> value} map. When there are too many keys, we need to evict the least-recently-used key therefore the key for which a get or put was called furthest into the past. As a result, we need to…

link Note, if get() is called for a timestamp that was not set, we need to find the latest value until that timestamp. In other words, say for a key, we have (1, val1), (2, val2, 2), (5, val3) where 1, 2, and 5 are timestamps. For that key, if get() is now called with…