Category: foundational_interview
-
LeetCode 348: Design Tic-Tac-Toe
link For each player we can keep four counts: (1) per row (2) per col (3) the major diagonal (4) the minor diagonal. After the move, if any of these four counts is , the player won. Operation Time Space __init__ move For better readability we could encapsulate counts in a Player class.
-
LeetCode 242: Valid Anagram
link Sort Sorted, anagrams must be identical. Time: , space: . Character map Every character of t must appear in s possibly in different order. Time: , space: .
-
LeetCode 266: Palindrome Permutation
link As we build {char -> count} map, we can find out the count of characters that appear odd number of times. For a palindrome there can be at most 1 such character. Time: , space: . We can also maintain a set of characters that appear odd number of times.
-
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.
unreasonably effective 