Category: hash_table
-
LeetCode 2262: Total Appeal of A String
link Try all substrings For a substring with end-points: (begin, end), length of the set() of characters is the appeal. Time: , space: . Prefix appeals Above, we are already quite efficient, taking only time per substring. So, if we want to be more efficient, say take total time, we cannot iterate over all substrings.…
-
LeetCode 523: Continuous Subarray Sum
link Try all subarrays A subarray has a start index and an end index. With all possible starts and ends we check if the sum is a multiple of . Time: , space: . Prefix sums Say is the sum of the subarray nums[j : k+1]. Then, it would be a good subarray if .…
-
LeetCode 1207: Unique Number of Occurrences
link We can create a map: {value -> count}. Each value having unique number of occurrences means: in the map, each value has a distinct count. In other words, the number of different counts in the map is same as the map size. Time: , space: .
-
LeetCode 409: Longest Palindrome
link We can have at most one character with odd number of occurrences in a palindrome. So, in one pass we find the count of characters that appear odd number of times. Time: , space: .
-
LeetCode 1915: Number of Wonderful Substrings
link For each substring, we can check if it is wonderful. Time: , space: . We can optimize is_wonderful by keeping track of the count of characters that appear odd number of times while building the char_count map. Using the same idea for each begin, we can get rid of is_wonderful. Time: , space: .
-
LeetCode 694: Number of Distinct Islands
link The challenge is to find a translation-invariant hash function for islands. We can consider each island having a bounding box around it and then we can translate that bounding box to the top-left of the grid. In this translated bounding box, if for two islands, the sequence of 1-cells are identical, we consider them…
-
LeetCode 791: Custom Sort String
link We can use counting sort. While processing order left-to-right, if order[i] = and appears times in s, we emit [c] * m. Time: , extra space: . Since the alphabet only consists of lowercase English letters, we can keep a list of length as the s_map.
-
LeetCode 299: Bulls and Cows
link If secret[i] = guess[i] that is a bull. So, we can process and exclude bull positions. In the remaining positions if guess[i] could be matched with a secret[j], that is a cow. So, we use two passes: (1) Bull pass (2) Cow pass. Time , space: . Note, len(secret) = len(guess). Say for a…
-
LeetCode 1086: High Five
link We create a map: {id -> minq(score)} and we cap the length of the minq at 5. In that way, in the end, we have the top five scores per id. Say len(items) = . There are two extreme cases: Time: , space: . Note, the heap plays a role only if there are…
-
LeetCode 1570: Dot Product of Two Sparse Vectors
link For two vectors and , the dot product . So, we represent a sparse vector as a map of nonzero values: {index -> value}. While computing dot product, we iterate over the vector that has a shorter sparse representation. Say len(nums) = and only values are nonzero. Operation Time Space __init__ dotProduct Follow up: What…
unreasonably effective 