Category: hash_table
-
LeetCode 609: Find Duplicate File in System
link We build a map: content -> [file_path]. If there are more than one files against a content, they are duplicates. Say there are files and the longest file path has length , then time: , space is proportional to the total number of characters including contents. Follow-up Imagine you are given a real file…
-
LeetCode 205: Isomorphic Strings
link Two strings are isomorphic if we can find a two-way mapping between their characters that makes the two strings identical. We keep two maps to validate the two-way mapping. Two maps we maintain are: s -> t and t -> s. For s[i] and t[i], either they have not been mapped yet or s[i]…
-
LeetCode 496: Next Greater Element I
link It’s a mapping problem: nums1 -> nums2 -> next_greater_element. To build the mapping nums2 -> next_greater_element, we take the approach in the next warmer day problem. Time: , space: .
-
LeetCode 359: Logger Rate Limiter
link For each unique message we keep the next valid timestamp. If a message is early, we simply discard it returning False. Otherwise, we update the next valid timestamp and return True. Time: , space: . We can also do the filtering based on elapsed time. Time: , space: . To optimize for space, we…
-
LeetCode 166: Fraction to Recurring Decimal
link The answer may look like: . For example: . Details For q, r = divmod(numerator, denominator), . Consequently, the longest length before a fractional digit repeats is . The get_repeated_decimal()‘s outer loop can have these many iterations. On each of these iterations, the inner while loop can run for iterations. So, time: , space:…
-
LeetCode 706: Design HashMap
link Indexed sequence Since , we can use a list of length to implement the API. Total space is . Operation Time Space put get remove Linked list We can use a doubly linked list where an item is . Total space is . Operation Time Space put get remove Indexed sequence of linked lists…
unreasonably effective 