-
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…
-
LeetCode 386: Lexicographical Numbers
link String sort Since there are digits in a number, time: , space: . DFS in a Trie There are digits in a number. So, building the trie and a DFS of the trie, both take time . Time: , space: . DFS in implicit Trie We could traverse the trie without explicitly building it.…
-
LeetCode 1065: Index Pairs of a String
link Substrings For each of the substrings, check if it is in the word_set. Say , , and the longest word has length . Time: , space: . Trie If a word is in the text, the word is a prefix of a suffix of the text. Since the text has only suffixes, from a…
-
LeetCode 14: Longest Common Prefix
link At an index, if all strings have the same character, set of these characters will have length one. Say there are strings and the shortest string has length . There are iterations. In each iteration both collecting characters at a given index and creating the set takes time . Time: , space: .
-
LeetCode 692: Top K Frequent Words
link Sorted frequency map We first create the frequency map: {word: count}. We then sort the map items with (- count) as the primary key and word as the secondary key. Finally, we return the first k of these sorted words as the answer. Assuming word comparison cost as constant, If there are words, time:…
-
LeetCode 212: Word Search II
link Backtrack For each word, we can search if it is in the board with backtracking. Trie We can build a trie out of the words to search, excluding a word if its first char does not appear in the board. While collecting words from the trie, we check against the board to see if…
-
LeetCode 211: Design Add and Search Words Data Structure
link Trie If word has “.”, we follow all available edges. Say the longest word has length . Operation Time Space insert search If there are no dots: . If all are dots: . Other cases should be in-between.
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 