Category: what_to_track
-
LeetCode 3016: Minimum Number of Pushes to Type Word II
link The more frequent a character is, the earlier in the mapping it should appear. There are only eight keys that can have character mapping. So, we keep assigning groups of eight characters to the eight keys in decreasing order of frequency. Say there are characters that need mapping with of them distinct. Time: ,…
-
LeetCode 383: Ransom Note
link We should find all characters of the ransomNote in the magazine. So, we use two passes: (1) For the magazine, build {char -> count} map (2) For each char in ransomNote, we try finding it in magazine. Say magazine has chars and ransomNote has chars. Time: , space: .
-
LeetCode 1010: Pairs of Songs With Total Durations Divisible by 60
link If , then . So, we keep track how many times we have seen . While considering , if we have seen before say times, then we have pairs with as the second element. Time: . Since there are only different remainders , space: .
-
LeetCode 1366: Rank Teams by Votes
link Say there are positions and represents the vote counts for at different positions. Like, got votes for position , got votes for position , etc. We can consider an extended pair: and sort these pairs by reverse-lexicographic of the first element and lexicographic of the second element. To have custom comparison while sorting we…
-
LeetCode 2131: Longest Palindrome by Concatenating Two Letter Words
link From palindrome’s mirror symmetry point of view, there are two types of elements: We find the longest length in two passes: (1) Build {element -> count} map (2) Depending on if it is a “repeated” element or not, we include them appropriately. If there are elements, time: , space: .
-
LeetCode 438: Find All Anagrams in a String
link An anagram of p is a window in s, so we can use sliding window. Variable-length window We expand the window until we get at least the required count for each character in p. Then we shrink to get the window size right. If the shrunk window still has all characters by the required…
-
LeetCode 387: First Unique Character in a String
link The first character in the string that appears once is our answer. So, we use two passes: (1) Create the map {char -> count} (2) Find first character having count = 1. Time: , space: .
-
LeetCode 895: Maximum Frequency Stack
link Since a tie for the maximum frequency must be broken in favor of recent-most value, we should maintain LIFO order per frequency. So, we need to maintain a stack per color. We shall use the below three pieces of information: Say there are numbers in the FreqStack having distinct values. So, . Operation Time…
-
LeetCode 49: Group Anagrams
link To group anagrams, we need a group id against which we can collect the anagrams. Sort Since all anagrams are identical after sorting, we can use sorted anagram as the group id. If there are strings and the longest string has length , time: , space: . Character frequency Sequence of character counts, in…
-
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.
unreasonably effective 