Hash Map & Set

Problem: Given an integer array nums and an integer target, return the indices of the two numbers that add up to target. Exactly one answer exists, and you may not use the same element twice.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 2 ≤ nums.length ≤ 10⁴ · -10⁹ ≤ nums[i] ≤ 10⁹ · -10⁹ ≤ target ≤ 10⁹ · Only one valid answer exists.

From brute force to the pattern: Checking every pair is O(n²). Sorting loses the original indices. A value → index map finds each complement in O(1), so one pass: O(n).

Spot it: "Find a pair that sums to a target" in an unsorted array. Sorting would lose the original indices, so instead remember every number you have seen in a hash map: value → index.

Key insight: For each number x, its partner must be target − x. If the partner was seen earlier, the map answers "where?" in O(1).

Approach:

1. Create an empty dictionary seen that maps a value to the index where it appeared.
2. Walk the array with its index i. For the current number x, compute need = target − x.
3. If need is already in seen, the pair is [seen[need], i]. Return it.
4. Otherwise store seen[x] = i and move on. Storing after checking stops x from pairing with itself.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # value -> index where we saw it
        seen = {}
        for i in range(len(nums)):
            x = nums[i]
            # the number that would complete the pair
            need = target - x
            if need in seen:
                # the partner appeared earlier: we are done
                return [seen[need], i]
            # remember x for the numbers that come later
            seen[x] = i
        # the problem guarantees an answer, so we never get here
        return []

What the code is doing, line by line:

1. seen = {}: an empty dictionary. Keys are numbers we have already passed, values are their indices.
2. for i in range(len(nums)): visit every position once; x = nums[i] is the number there.
3. need = target - x: the only value that can pair with x.
4. if need in seen: a dictionary lookup is O(1) on average. If the partner was seen, return its index and ours.
5. seen[x] = i: we store x only after the check, so an element can never be paired with itself (e.g. target = 6, x = 3 does not match its own entry).
6. return []: unreachable for valid input, but keeps the function returning a list on every path.

Dry run on the example:

nums = [2, 7, 11, 15], target = 9 (LeetCode Example 1). Returns [0, 1].

Edge cases to test:

• Two equal numbers form the pair, e.g. [3, 3], target 6.
• Negative numbers.
• Using the same element twice is not allowed (that's why we look up before storing).

Complexity: O(n) time (one pass, O(1) lookups), O(n) space for the map.

Problem: Group the strings that are anagrams of each other. Return the groups in any order.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ strs.length ≤ 10⁴ · 0 ≤ strs[i].length ≤ 100 · strs[i] consists of lowercase English letters.

From brute force to the pattern: Comparing every pair of words for being anagrams is O(n² · k). One canonical key per word puts each word straight into its group: O(n · k log k) (or O(n · k) with count keys).

Spot it: "Group items that share a property" → a hash map from a canonical key to a list. All anagrams sort to the same string, so "".join(sorted(word)) is a perfect key.

Approach:

1. For each word, compute key = "".join(sorted(word)).
2. Append the word to groups[key] (creating the list the first time).
3. Return all the lists.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = {}
        for word in strs:
            # anagrams have the same letters, so they sort to the same key
            key = "".join(sorted(word))
            if key not in groups:
                groups[key] = []
            groups[key].append(word)
        return list(groups.values())

What the code is doing, line by line:

1. sorted(word) returns a list of characters in order; "".join(...) glues them back into a string. Lists can't be dictionary keys, but strings can.
2. if key not in groups: groups[key] = []: start a new group the first time a key appears (collections.defaultdict(list) does this automatically).
3. groups[key].append(word): add the word to its group.
4. list(groups.values()): just the groups, without their keys.
5. A faster key is a tuple of 26 letter counts: O(k) per word instead of O(k log k).

Dry run on the example:

strs = ["eat", "tea", "tan", "ate", "nat", "bat"] (LeetCode Example 1). Returns [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].

Edge cases to test:

• An empty string "" forms its own group.
• A single word.
• No two words are anagrams → every group has one word.

Complexity: O(n · k log k) time for n words of length up to k, O(n · k) space.

Problem: Return the length of the longest run of consecutive integers that can be formed from nums (in any order), in O(n) time.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 0 ≤ nums.length ≤ 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Sorting and scanning is O(n log n); walking upward from every number is O(n²). Starting only at run beginnings walks each number once: O(n).

Spot it: O(n) rules out sorting. A set lets you ask "is x + 1 here?" in O(1). The trick is to count each run only once, from its smallest number.

Key insight: x starts a run exactly when x − 1 is not in the set. Counting only from run starts means each number is stepped over at most once in total.

Approach:

1. Put all numbers in a set (this also drops duplicates).
2. For each x in the set: skip it if x − 1 is present (it is in the middle of a run).
3. Otherwise count upward x, x + 1, x + 2, … while the numbers exist; update the best length.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        values = set(nums)
        best = 0
        for x in values:
            if x - 1 in values:
                continue                  # not the start of a run
            # x starts a run: walk it upward
            length = 1
            while x + length in values:
                length = length + 1
            best = max(best, length)
        return best

What the code is doing, line by line:

1. values = set(nums): O(1) membership tests; duplicates disappear.
2. if x - 1 in values: continue: someone smaller will count this run, so skip.
3. while x + length in values: extend the run one number at a time.
4. Every number is walked over only from its run's start, so the total work is O(n) even though there's a loop inside a loop.

Dry run on the example:

nums = [100, 4, 200, 1, 3, 2] (LeetCode Example 1). Returns 4 (the run 1, 2, 3, 4).

(A set's iteration order isn't guaranteed; the rows follow the input order for readability. The answer doesn't depend on the order.)

Edge cases to test:

• An empty array → 0.
• Duplicates, e.g. [1, 2, 2, 3] → 3.
• Negative numbers.

Complexity: O(n) time, O(n) space.

Problem: Return True if any value appears at least twice in nums, otherwise False.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁹ ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Comparing every pair is O(n²); sorting and checking neighbours is O(n log n). A set answers "seen before?" in O(1): O(n).

Spot it: "Have I seen this before?" is the textbook question a hash set answers in O(1).

Approach:

1. Keep a set seen of values already passed.
2. For each number: if it is in seen, return True; otherwise add it.
3. If the loop finishes, every value was unique: False.

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for x in nums:
            if x in seen:
                return True      # x appeared earlier
            seen.add(x)
        return False

What the code is doing, line by line:

1. seen = set(): an empty hash set. x in seen and seen.add(x) are both O(1) on average.
2. if x in seen: return True: stop at the first repeat; no need to look further.
3. seen.add(x): remember x for the rest of the scan.
4. return False: all values were distinct. (One-liner alternative: len(set(nums)) < len(nums), but it can't stop early.)

Dry run on the example:

nums = [1, 2, 3, 1] (LeetCode Example 1). Returns True.

Edge cases to test:

• A single element → False.
• The duplicate appears at the very end.
• Negative numbers.

Complexity: O(n) time, O(n) space. (Sorting first is O(n log n) time but O(1) extra space.)

Problem: Return True if t is an anagram of s: the same letters, each used the same number of times, in any order.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length, t.length ≤ 5 * 10⁴ · s and t consist of lowercase English letters.

From brute force to the pattern: Sorting both strings and comparing is O(n log n). Counting letters is O(n), and for lowercase letters an array of 26 counts works too.

Spot it: Order doesn't matter, only how many of each letter. A count map (letter → count) is the fingerprint.

Approach:

1. Different lengths can't be anagrams.
2. Count every letter of s (+1) and every letter of t (−1) in one dictionary.
3. Anagrams cancel out: every count must end at 0.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        count = {}
        for i in range(len(s)):
            # +1 for letters of s, -1 for letters of t
            count[s[i]] = count.get(s[i], 0) + 1
            count[t[i]] = count.get(t[i], 0) - 1
        for letter in count:
            if count[letter] != 0:
                return False     # this letter is used a different number of times
        return True

What the code is doing, line by line:

1. if len(s) != len(t): return False: a quick exit, and it also lets one loop walk both strings at once.
2. count.get(key, 0): returns 0 for a letter not seen yet, avoiding a KeyError.
3. + 1 for s[i], - 1 for t[i]: a letter that appears equally often in both ends at 0.
4. if count[letter] != 0: return False: some letter is over- or under-used.
5. collections.Counter(s) == Counter(t) is the same idea in one line.

Dry run on the example:

s = "rat", t = "car" (LeetCode Example 2). Returns False.

c is −1 (and t is 1), so the answer is False.

Edge cases to test:

• Different lengths → False immediately.
• Same letters with different counts, e.g. "aab" vs "abb".
• Unicode letters (a dictionary handles them; a 26-array doesn't).

Complexity: O(n) time, O(k) space for k distinct letters (at most 26 for lowercase English).

Problem: Return True if ransomNote can be built from the letters of magazine, each magazine letter used at most once.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ ransomNote.length, magazine.length ≤ 10⁵ · ransomNote and magazine consist of lowercase English letters.

From brute force to the pattern: For each note letter, searching and removing it from the magazine string is O(m · n). Counting once and decrementing is O(m + n).

Spot it: A supply-and-demand question about letter counts → count the magazine's letters in a map, then use them up.

Approach:

1. Count every letter in magazine.
2. For each letter of ransomNote: if none of it is left, return False; otherwise use one (decrement).
3. If every letter was available, return True.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        available = {}
        for ch in magazine:
            available[ch] = available.get(ch, 0) + 1
        for ch in ransomNote:
            if available.get(ch, 0) == 0:
                return False          # we ran out of this letter
            available[ch] = available[ch] - 1
        return True

What the code is doing, line by line:

1. available: how many of each letter the magazine offers.
2. available.get(ch, 0) == 0: either the magazine never had ch, or every copy is already used.
3. available[ch] = available[ch] - 1: cut out one copy.
4. return True: the whole note was covered.

Dry run on the example:

ransomNote = "aa", magazine = "aab" (LeetCode Example 3). Returns True.

Every letter was available → True. With magazine = "ab" the second a would find 0 left → False.

Edge cases to test:

• The note needs more copies of a letter than the magazine has.
• An empty note → True.
• Identical strings → True.

Complexity: O(m + n) time, O(k) space for k distinct letters.

Problem: jewels lists the stone types that are jewels (case-sensitive). Return how many of your stones are jewels.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ jewels.length, stones.length ≤ 50 · jewels and stones consist of only English letters. · All the characters of jewels are unique.

From brute force to the pattern: Checking each stone against the jewels string is O(j · s). A set makes it O(j + s).

Spot it: Many "is this one of those?" checks → turn the list of types into a set so each check is O(1) instead of scanning jewels.

Approach:

1. Build jewel_set = set(jewels).
2. Count the stones whose type is in the set.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewel_set = set(jewels)
        count = 0
        for stone in stones:
            if stone in jewel_set:
                count = count + 1
        return count

What the code is doing, line by line:

1. set(jewels): each character of the string becomes a member; lookups are O(1).
2. for stone in stones: look at every stone you own.
3. if stone in jewel_set: case-sensitive, so 'a' and 'A' are different types.

Dry run on the example:

jewels = "aA", stones = "aAAbbbb" (LeetCode Example 1). Returns 3.

Edge cases to test:

• No jewels among the stones → 0.
• Case matters: a and A are different.
• Every stone is a jewel.

Complexity: O(j + s) time, O(j) space for the set.

Problem: Using the letters of text at most once each, how many copies of the word "balloon" can you form?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ text.length ≤ 10⁴ · text consists of lower case English letters only.

From brute force to the pattern: Repeatedly removing the letters of "balloon" from the text is O(n · words). Counting once and dividing is O(n).

Spot it: Supply vs demand of letter counts → count map. "balloon" needs b, a, n once and l, o twice; the scarcest letter, relative to its need, limits the answer.

Approach:

1. Count the letters of text.
2. Count the letters needed for one "balloon": {b: 1, a: 1, l: 2, o: 2, n: 1}.
3. For each needed letter, have // need is how many words that letter alone allows. The answer is the minimum over all letters.

class Solution:
    def maxNumberOfBalloons(self, text: str) -> int:
        have = {}
        for ch in text:
            have[ch] = have.get(ch, 0) + 1
        need = {"b": 1, "a": 1, "l": 2, "o": 2, "n": 1}
        best = len(text)          # an upper bound to shrink
        for ch in need:
            # how many words this letter alone could supply
            best = min(best, have.get(ch, 0) // need[ch])
        return best

What the code is doing, line by line:

1. have: letter counts of the input.
2. need: written out by hand; l and o appear twice in "balloon".
3. have.get(ch, 0) // need[ch]: integer division, e.g. 3 ls make only 1 word (3 // 2).
4. best = min(...): the bottleneck letter decides.

Dry run on the example:

text = "loonbalxballpoon" (LeetCode Example 2). Returns 2.

The minimum is 2.

Edge cases to test:

• A missing letter → 0.
• Only one l or one o → 0.
• Lots of extra unrelated letters.

Complexity: O(n) time, O(1) space (at most 26 letters).

Problem: s and t are isomorphic if the characters of s can be replaced to get t: every occurrence of a character maps to the same character, and no two characters map to the same one. Check it.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ s.length ≤ 5 * 10⁴ · t.length == s.length · s and t consist of any valid ascii character.

From brute force to the pattern: Checking every pair of positions for consistency is O(n²). Two dictionaries (one per direction) check each position in O(1): O(n).

Spot it: A consistent character-to-character mapping is a dictionary. "No two map to the same" means it must also be consistent backwards, so keep a second map for t → s.

Approach:

1. Walk both strings together, pairing a = s[i] with b = t[i].
2. If a already maps to something other than b, fail. If b is already the image of something other than a, fail.
3. Otherwise record a → b and b → a.

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_to_t = {}
        t_to_s = {}
        for i in range(len(s)):
            a = s[i]
            b = t[i]
            if a in s_to_t and s_to_t[a] != b:
                return False      # a was already promised to a different letter
            if b in t_to_s and t_to_s[b] != a:
                return False      # b is already taken by a different letter
            s_to_t[a] = b
            t_to_s[b] = a
        return True

What the code is doing, line by line:

1. s_to_t: where each letter of s goes. t_to_s: which letter of s claimed each letter of t.
2. if a in s_to_t and s_to_t[a] != b: the same a would have to become two different letters.
3. if b in t_to_s and t_to_s[b] != a: two different letters of s would both become b. One map alone can't catch this (e.g. "ab" → "aa").
4. s_to_t[a] = b, t_to_s[b] = a: record the pair (harmless if it was already there).

Dry run on the example:

s = "badc", t = "baba". Returns False (b and d would both map to b).

Edge cases to test:

• Two different letters mapping to the same letter, e.g. "ab" → "aa" → False.
• Identical strings → True.
• Single characters.

Complexity: O(n) time, O(k) space for k distinct characters.

Problem: Does s (words separated by single spaces) follow pattern? Each letter must map to exactly one word and each word to exactly one letter.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ pattern.length ≤ 300 · pattern contains only lower-case English letters. · 1 ≤ s.length ≤ 3000 · s contains only lowercase English letters and spaces ' '. · s does not contain any leading or trailing spaces. · All the words in s are separated by a single space.

From brute force to the pattern: Comparing every pair of positions is O(n²). Two maps check the one-to-one mapping in a single pass: O(n).

Spot it: A one-to-one (bijective) mapping → two dictionaries, letter → word and word → letter, exactly like LeetCode 205.

Approach:

1. Split s into words. If the count differs from len(pattern), return False.
2. Walk letter/word pairs; reject any pair that contradicts an existing mapping in either direction.
3. Record both directions and continue.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(words) != len(pattern):
            return False
        letter_to_word = {}
        word_to_letter = {}
        for i in range(len(pattern)):
            letter = pattern[i]
            word = words[i]
            if letter in letter_to_word and letter_to_word[letter] != word:
                return False
            if word in word_to_letter and word_to_letter[word] != letter:
                return False
            letter_to_word[letter] = word
            word_to_letter[word] = letter
        return True

What the code is doing, line by line:

1. s.split(): breaks the sentence at spaces into a list of words.
2. if len(words) != len(pattern): every letter needs exactly one word.
3. The two if checks catch "one letter, two words" and "two letters, one word".
4. letter_to_word[letter] = word, word_to_letter[word] = letter: remember the pairing in both directions.

Dry run on the example:

pattern = "abba", s = "dog cat cat fish" (LeetCode Example 2). Returns False.

Edge cases to test:

• Different numbers of letters and words → False.
• Different letters mapping to the same word → False.
• A single letter and a single word.

Complexity: O(n) time and space, where n is the length of s.

Problem: The majority element appears more than n / 2 times, and it always exists. Return it.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: n == nums.length · 1 ≤ n ≤ 5 * 10⁴ · -10⁹ ≤ nums[i] ≤ 10⁹ · The input is generated such that a majority element will exist in the array.

From brute force to the pattern: Counting the occurrences of every value separately is O(n²); sorting and taking the middle is O(n log n). A count map is O(n), and voting is O(n) with O(1) space.

Spot it: "How often does each value appear?" → a count map; return the value whose count passes n // 2. The follow-up asks for O(1) space, which is Boyer–Moore voting (shown second).

Approach:

1. Count map version: count each value; as soon as a count exceeds n // 2, return that value.
2. Voting version: keep a candidate and a votes counter. When votes is 0, adopt the current value as candidate.
3. Add a vote if the value equals the candidate, otherwise remove one. Pairs of different values cancel out, and the majority can't be fully cancelled.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # hash-map version: O(n) time, O(n) space
        count = {}
        for x in nums:
            count[x] = count.get(x, 0) + 1
            if count[x] > len(nums) // 2:
                return x
        return -1

    def majorityElementVoting(self, nums: List[int]) -> int:
        # Boyer-Moore voting: O(n) time, O(1) space
        candidate = None
        votes = 0
        for x in nums:
            if votes == 0:
                candidate = x            # nobody is ahead: x becomes the candidate
            if x == candidate:
                votes = votes + 1
            else:
                votes = votes - 1        # x cancels one vote of the candidate
        return candidate

What the code is doing, line by line:

1. count[x] = count.get(x, 0) + 1: tally each value.
2. if count[x] > len(nums) // 2: return x: the first value to pass half is the majority, so we can stop early.
3. Voting: if votes == 0: candidate = x: the previous candidate was cancelled out, so start fresh with x.
4. votes + 1 for a match, votes - 1 otherwise. Each −1 pairs one majority element with one other element. The majority has more than half of the elements, so it always has votes left at the end.

Dry run on the example:

nums = [2, 2, 1, 1, 1, 2, 2] (LeetCode Example 2), using the voting version. Returns 2.

Edge cases to test:

• A single element.
• The majority at the start or the end.
• Negative numbers.

Complexity: Count map: O(n) time and space. Voting: O(n) time, O(1) space.

Problem: Check whether a partially filled 9 × 9 Sudoku board is valid: no digit may repeat within a row, a column, or a 3 × 3 box. Empty cells are ".". (It doesn't have to be solvable.)

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: board.length == 9 · board[i].length == 9 · board[i][j] is a digit 1-9 or '.'.

From brute force to the pattern: Re-scanning the row, column and box of every filled cell is O(81 · 27), which is small but repetitive. Twenty-seven sets check each cell in O(1), in one pass.

Spot it: "No repeats within a group" → a set per group. A cell belongs to row r, column c and box (r // 3, c // 3); check all three sets before adding the digit.

Approach:

1. Make 9 row sets, 9 column sets and 9 box sets.
2. For every filled cell: compute box = (r // 3) * 3 + c // 3.
3. If the digit is already in its row, column or box set, return False.
4. Otherwise add it to all three. If the scan finishes, return True.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        for r in range(9):
            for c in range(9):
                digit = board[r][c]
                if digit == ".":
                    continue
                # boxes are numbered 0..8, left to right, top to bottom
                box = (r // 3) * 3 + c // 3
                if digit in rows[r] or digit in cols[c] or digit in boxes[box]:
                    return False
                rows[r].add(digit)
                cols[c].add(digit)
                boxes[box].add(digit)
        return True

What the code is doing, line by line:

1. [set() for _ in range(9)]: nine separate sets. ([set()] * 9 would be nine references to the same set.)
2. if digit == ".": continue: empty cells can't conflict.
3. box = (r // 3) * 3 + c // 3: r // 3 is the band (0–2) and c // 3 the stack (0–2), so e.g. cell (4, 7) is box 1 * 3 + 2 = 5.
4. if digit in rows[r] or ...: a repeat in any of the three groups breaks the rules.
5. Add the digit to all three sets so later cells can be checked against it.

Dry run on the example:

LeetCode Example 2: the valid example board, except its top-left 5 is replaced by 8. Returns False. Scanning row by row, the first conflict appears at (2, 2):

The 8 at (2, 2) repeats the 8 at (0, 0) inside the same top-left box, so the scan stops there.

Edge cases to test:

• An empty board → True.
• A duplicate only inside a box.
• A valid board that isn't solvable still counts as valid.

Complexity: O(81) = O(1) for a fixed 9 × 9 board (O(n²) for an n × n one), O(1) space.

Problem: Return all values that appear more than ⌊n/3⌋ times.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 5 * 10⁴ · -10⁹ ≤ nums[i] ≤ 10⁹

From brute force to the pattern: A Counter is O(n) time but O(n) space; two-candidate voting is O(1) space.

Spot it: A hash map of counts solves it directly in O(n) space. The follow-up asks for O(1) space: at most two values can pass n/3, so keep two candidates with counters (Boyer–Moore voting), cancelling a triple of distinct values each time, then count the candidates to confirm.

Why not another pattern? Sorting and scanning is O(n log n).

Approach:

1. Two candidate slots with counts.
2. For each x: if it matches a candidate, increment; else if a slot is empty, take it; else decrement both (cancel three distinct values).
3. Count the surviving candidates in a second pass; keep those above n / 3.

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        cand1, cand2, c1, c2 = None, None, 0, 0
        for x in nums:
            if x == cand1:
                c1 += 1
            elif x == cand2:
                c2 += 1
            elif c1 == 0:
                cand1, c1 = x, 1  # take the empty slot
            elif c2 == 0:
                cand2, c2 = x, 1
            else:
                c1 -= 1  # x and both candidates cancel out
                c2 -= 1
        return [c for c in (cand1, cand2) if c is not None and nums.count(c) > len(nums) // 3]  # verify

What the code is doing, line by line:

1. Each cancellation removes three different values; a value with more than n/3 copies can't be fully cancelled.
2. The survivors are only candidates, so a second pass checks their real counts.
3. The is not None check skips an unused slot.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No majority → [].
• Two majority values.
• All equal.

Complexity: O(n) time, O(1) space.

Problem: Return the hint xAyB: x digits right in the right place, y right digits in the wrong place.

Solve it on LeetCode ↗

Constraints: 1 ≤ secret.length, guess.length ≤ 1000 · secret.length == guess.length · secret and guess consist of digits only.

From brute force to the pattern: Pairing digits by searching is O(n²); counting is O(n).

Spot it: Count matching positions directly; for the rest, the number of shared digits is Σ min(count₁[d], count₂[d]) → counting with a hash map.

Why not another pattern? Matching each unmatched digit by searching the other string is O(n²).

Approach:

1. For each position: equal → bull; otherwise count the secret digit and the guess digit separately.
2. Cows = Σ min(secret_count[d], guess_count[d]).

from collections import Counter

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls = 0
        left_s = Counter()
        left_g = Counter()
        for a, b in zip(secret, guess):
            if a == b:
                bulls += 1  # right digit, right place
            else:
                left_s[a] += 1  # unmatched digits on each side
                left_g[b] += 1
        cows = sum(min(left_s[d], left_g[d]) for d in left_s)  # shared digits in wrong places
        return f"{bulls}A{cows}B"

What the code is doing, line by line:

1. Bulls are removed before counting cows, so a digit is never both.
2. Each digit can be a cow as many times as it appears on both sides: the minimum of the two counts.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Repeated digits.
• All bulls.
• No matches.

Complexity: O(n) time, O(1) space (10 digits).

Problem: Draw a vertical line through a brick wall crossing the fewest bricks (not along the outer edges). Return that number.

Solve it on LeetCode ↗

Constraints: n == wall.length · 1 ≤ n ≤ 10⁴ · 1 ≤ wall[i].length ≤ 10⁴ · 1 ≤ sum(wall[i].length) ≤ 2 * 10⁴ · sum(wall[i]) is the same for each row i. · 1 ≤ wall[i][j] ≤ 2³¹ - 1

From brute force to the pattern: Testing every x up to the width is too slow; counting edge positions is linear in the number of bricks.

Spot it: A line crosses every row except those with a brick edge at its position. Count, with a hash map, how many rows have an edge at each position (prefix sums of brick widths); the answer is rows − max count.

Why not another pattern? Trying every x position up to the wall width (up to 2³¹) is impossible.

Approach:

1. For each row, walk the bricks except the last, accumulating the position; increment edges[position].
2. Return len(wall) − max(edges.values(), default=0).

from collections import Counter

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        edges = Counter()  # x position -> rows with a brick edge there
        for row in wall:
            x = 0
            for width in row[:-1]:  # skip the wall's right edge
                x += width
                edges[x] += 1
        return len(wall) - max(edges.values(), default=0)  # cross the bricks of all other rows

What the code is doing, line by line:

1. Only positions where some row has an edge are worth considering.
2. The last brick's edge is the wall's border, which isn't allowed, so it's skipped.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Every row is one brick → crosses all rows.
• All rows share an edge → 0.
• One row.

Complexity: O(total bricks) time and space.

Problem: Given "count domain" entries, return the visit count of every domain and subdomain (any order).

Solve it on LeetCode ↗

Constraints: 1 ≤ cpdomain.length ≤ 100 · 1 ≤ cpdomain[i].length ≤ 100 · cpdomain[i] follows either the "repi d1i.d2i.d3i" format or the "repi d1i.d2i" format. · repi is an integer in the range [1, 10⁴]. · d1i, d2i, and d3i consist of lowercase English letters.

From brute force to the pattern: This is already linear; the hash map is the whole idea.

Spot it: A visit to a.b.c is also a visit to b.c and c: accumulate into a hash map for every dot-suffix.

Why not another pattern? Nothing smarter is needed; the work is proportional to the input size.

Approach:

1. Split each entry into count and domain.
2. For each suffix after a dot (and the full domain), add the count.
3. Format "count domain" for each key.

from collections import Counter

class Solution:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        visits = Counter()
        for entry in cpdomains:
            count, domain = entry.split()
            parts = domain.split(".")
            for i in range(len(parts)):
                visits[".".join(parts[i:])] += int(count)  # every parent domain is visited too
        return [f"{c} {d}" for d, c in visits.items()]

What the code is doing, line by line:

1. parts[i:] gives the domain itself (i = 0) and each parent domain.
2. Counts for the same domain from different entries add up.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Top-level domains shared by many entries.
• One entry.
• Domains with many levels.

Complexity: O(total characters) time and space.

Problem: Apply simultaneous, non-overlapping replacements: at indices[i], if sources[i] matches the original s, replace it with targets[i].

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 1000 · k == indices.length == sources.length == targets.length · 1 ≤ k ≤ 100 · 0 ≤ indexes[i] < s.length · 1 ≤ sources[i].length, targets[i].length ≤ 50 · s consists of only lowercase English letters. · sources[i] and targets[i] consist of only lowercase English letters.

From brute force to the pattern: Applying replacements one by one in place shifts indices and needs care; one rebuild pass is simplest.

Spot it: Replacements change lengths, so apply them by rebuilding the string in one left-to-right pass. A hash map from index to the valid replacement says what to do at each position.

Why not another pattern? Replacing in place shifts the later indices; doing them right-to-left works but needs sorting.

Approach:

1. For each operation whose source matches at its index, store todo[index] = (len(source), target).
2. Walk i through s: if i is in todo, append the target and jump past the source; else append s[i].

class Solution:
    def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
        todo = {}  # index -> (length to replace, replacement)
        for i, src, tgt in zip(indices, sources, targets):
            if s.startswith(src, i):
                todo[i] = (len(src), tgt)  # matches the original string
        out = []
        i = 0
        while i < len(s):
            if i in todo:
                length, tgt = todo[i]
                out.append(tgt)
                i += length  # skip the replaced part
            else:
                out.append(s[i])
                i += 1
        return "".join(out)

What the code is doing, line by line:

1. Matching is checked against the original string, as required (startswith(src, i)).
2. Building a new list keeps all original indices valid while replacing.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A source that doesn't match (skip it).
• Indices given out of order.
• Replacements at the very end.

Complexity: O(n + Σ source lengths + Σ target lengths) time and space.

Problem: Return the minimum area of a rectangle (any rotation) with corners among the points, or 0.

Solve it on LeetCode ↗

Constraints: 1 ≤ points.length ≤ 50 · points[i].length == 2 · 0 ≤ xi, yi ≤ 4 * 10⁴ · All the given points are unique.

From brute force to the pattern: All 4-point subsets is O(n⁴) with a rectangle test; grouping diagonals is about O(n²).

Spot it: Two segments are the diagonals of a rectangle iff they have the same midpoint and the same length. Group all point pairs in a hash map by (sum of coordinates, squared length); any two pairs in a group form a rectangle.

Why not another pattern? Trying all 4-point combinations is O(n⁴).

Approach:

1. For every pair (p, q): key = (px + qx, py + qy, |p − q|²); append the pair.
2. Within a group, for pairs (p, q) and (r, s): area = |p − r| · |p − s|.
3. Return the minimum area (0 if none).

from collections import defaultdict
from math import dist

class Solution:
    def minAreaFreeRect(self, points: List[List[int]]) -> float:
        groups = defaultdict(list)  # (2 * midpoint, squared diagonal length) -> point pairs
        for i in range(len(points)):
            for j in range(i + 1, len(points)):
                (x1, y1), (x2, y2) = points[i], points[j]
                key = (x1 + x2, y1 + y2, (x1 - x2) ** 2 + (y1 - y2) ** 2)
                groups[key].append((points[i], points[j]))
        best = float("inf")
        for pairs in groups.values():
            for a in range(len(pairs)):
                for b in range(a + 1, len(pairs)):
                    p, q = pairs[a]
                    r, s = pairs[b]  # same midpoint and length: a rectangle p, r, q, s
                    best = min(best, dist(p, r) * dist(p, s))  # two adjacent sides
        return best if best < float("inf") else 0.0

What the code is doing, line by line:

1. Using x1 + x2 (twice the midpoint) keeps keys as integers.
2. Equal diagonals bisecting each other make a rectangle; its sides are p → r and p → s.
3. Groups are usually small, so the pair-of-pairs loop is cheap in practice.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No rectangle → 0.
• Axis-aligned rectangles.
• Collinear points.

Complexity: O(n²) to group, plus O(Σ group²) to combine (O(n⁴) worst case, rare).

Problem: Operations: swap any two characters; or swap all occurrences of two existing letters. Can word1 become word2?

Solve it on LeetCode ↗

Constraints: 1 ≤ word1.length, word2.length ≤ 10⁵ · word1 and word2 contain only lowercase English letters.

From brute force to the pattern: Simulating operations is hopeless; comparing two invariants is O(n).

Spot it: Swaps make order irrelevant; the second operation permutes which letter has which count. So the strings are close iff they use the same letters and the same list of counts → compare with hash maps.

Why not another pattern? Searching sequences of operations is pointless once the invariants are clear.

Approach:

1. Count letters of both words.
2. Same key sets, and same sorted count values → true.

from collections import Counter

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        c1 = Counter(word1)
        c2 = Counter(word2)
        same_letters = c1.keys() == c2.keys()  # operation 2 can't create new letters
        same_counts = sorted(c1.values()) == sorted(c2.values())  # counts can be reassigned between letters
        return same_letters and same_counts

What the code is doing, line by line:

1. Operation 1 lets us reorder freely, so only counts matter.
2. Operation 2 swaps the counts of two letters that both exist, so counts can be permuted among the same letter set.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Different lengths → false.
• A letter in one word only → false.
• Same counts on different letters.

Complexity: O(n) time, O(1) space (26 letters).

Problem: The beauty of a string is (most frequent count − least frequent count). Sum the beauty of all substrings.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 500 · s consists of only lowercase English letters.

From brute force to the pattern: Recounting each substring is O(n³); incremental counts make it O(26 n²).

Spot it: There are O(n²) substrings; extending each start one character at a time keeps a frequency table, so each substring costs O(26).

Why not another pattern? Counting each substring from scratch is O(n³).

Approach:

1. For each start i: a fresh count array.
2. For each end j ≥ i: add s[j]; add max(counts) − min(non-zero counts).

class Solution:
    def beautySum(self, s: str) -> int:
        total = 0
        for i in range(len(s)):
            count = [0] * 26  # letter counts of s[i..j]
            for j in range(i, len(s)):
                count[ord(s[j]) - 97] += 1
                present = [c for c in count if c]
                total += max(present) - min(present)  # beauty of s[i..j]
        return total

What the code is doing, line by line:

1. Extending the end by one only changes one count.
2. Letters that don't appear (count 0) are ignored for the minimum.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All same letter → 0.
• Length 1.
• Two letters alternating.

Complexity: O(26 · n²) time, O(1) space.

Problem: Count pairs of rectangles with the same width-to-height ratio.

Solve it on LeetCode ↗

Constraints: n == rectangles.length · 1 ≤ n ≤ 10⁵ · rectangles[i].length == 2 · 1 ≤ widthi, heighti ≤ 10⁵

From brute force to the pattern: Comparing every pair is O(n²); grouping is O(n).

Spot it: Group rectangles by their reduced ratio in a hash map; a group of size c contributes c(c − 1)/2 pairs.

Why not another pattern? Comparing all pairs is O(n²); float ratios risk precision errors, so use reduced integer pairs.

Approach:

1. For each rectangle, key = (w / g, h / g) with g = gcd(w, h).
2. Before counting it, add the number already seen with that key (counts pairs as they form).

from collections import Counter
from math import gcd

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        seen = Counter()
        pairs = 0
        for w, h in rectangles:
            g = gcd(w, h)
            key = (w // g, h // g)  # exact ratio, no floating point
            pairs += seen[key]  # pairs with every earlier rectangle of this ratio
            seen[key] += 1
        return pairs

What the code is doing, line by line:

1. Dividing by the gcd gives every equal ratio the same key.
2. Adding the earlier count before incrementing counts each pair once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All the same ratio.
• All different.
• Large dimensions (floats would be risky).

Complexity: O(n log V) time, O(n) space.

Problem: changed is an array plus all its doubles, shuffled. Return the original array, or [].

Solve it on LeetCode ↗

Constraints: 1 ≤ changed.length ≤ 10⁵ · 0 ≤ changed[i] ≤ 10⁵

From brute force to the pattern: Trying pairings by search is exponential; sorted greedy with counts is O(n log n).

Spot it: The smallest remaining value can't be a double of anything left, so it must be original and its double must exist. Process values in sorted order with a count map.

Why not another pattern? Pairing greedily in arbitrary order can pair x with x/2 when x should be original.

Approach:

1. If the length is odd, return [].
2. Count values; for each x in increasing order with count[x] > 0: need count[2x] ≥ count[x] (zeros pair with zeros).
3. Take count[x] copies of x, subtract from count[2x].

from collections import Counter

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        if len(changed) % 2:
            return []
        count = Counter(changed)
        original = []
        for x in sorted(count):  # smallest first: it can't be someone's double
            if count[x] == 0:
                continue
            if x == 0:
                if count[0] % 2:
                    return []
                original += [0] * (count[0] // 2)  # zeros pair with zeros
                continue
            if count[2 * x] < count[x]:
                return []  # not enough doubles
            original += [x] * count[x]
            count[2 * x] -= count[x]
        return original

What the code is doing, line by line:

1. The smallest value can only be an original element (its half would be smaller).
2. All copies of x are handled at once using the counts.
3. Zero is its own double, so zeros must come in pairs.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Odd length → [].
• Zeros.
• Chains like 1, 2, 2, 4.

Complexity: O(n log n) time, O(n) space.

Problem: Return every number that appears exactly once and whose neighbours x − 1, x + 1 don't appear.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁶

From brute force to the pattern: Checking neighbours by scanning the array is O(n²); a counter is O(n).

Spot it: Both conditions are lookups → one counter answers each check in O(1).

Why not another pattern? Sorting and checking neighbours works in O(n log n); the counter is O(n).

Approach:

1. Count all numbers.
2. Keep x if count[x] == 1 and x − 1, x + 1 aren't in the counter.

from collections import Counter

class Solution:
    def findLonely(self, nums: List[int]) -> List[int]:
        count = Counter(nums)
        return [x for x in count if count[x] == 1 and x - 1 not in count and x + 1 not in count]  # alone and no neighbours

What the code is doing, line by line:

1. Membership tests on the counter are O(1).
2. Iterating over the counter's keys visits each distinct value once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Duplicates aren't lonely.
• Negative numbers.
• Consecutive runs.

Complexity: O(n) time and space.

Problem: Return [players with no losses, players with exactly one loss], each sorted, among players who played.

Solve it on LeetCode ↗

Constraints: 1 ≤ matches.length ≤ 10⁵ · matches[i].length == 2 · 1 ≤ winneri, loseri ≤ 10⁵ · winneri != loseri · All matches[i] are unique.

From brute force to the pattern: Counting losses per player by scanning all matches is quadratic; one pass with a map is linear.

Spot it: A hash map of losses, with winners inserted at 0 so they're known to have played.

Why not another pattern? Scanning matches per player is O(players · matches).

Approach:

1. For each match: losses.setdefault(winner, 0), losses[loser] += 1.
2. Collect sorted players with 0 and with 1.

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        losses = {}
        for winner, loser in matches:
            losses.setdefault(winner, 0)  # played, maybe never lost
            losses[loser] = losses.get(loser, 0) + 1
        never = sorted(p for p, c in losses.items() if c == 0)
        once = sorted(p for p, c in losses.items() if c == 1)
        return [never, once]

What the code is doing, line by line:

1. Only players who appear in some match are in the map.
2. Sorting each list at the end gives the required order.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A player who only won.
• Nobody with one loss → empty list.
• One match.

Complexity: O(m + p log p) time, O(p) space.

Problem: A pair i < j is bad if j − i != nums[j] − nums[i]. Count bad pairs.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: All pairs is O(n²); key counting is O(n).

Spot it: Rearranging the good condition gives nums[i] − i == nums[j] − j: the same key. Count good pairs per key with a hash map and subtract from all pairs.

Why not another pattern? Checking all pairs is O(n²).

Approach:

1. For each j, key = nums[j] − j; good pairs with earlier equal keys = seen[key].
2. Bad = j − seen[key] for this j; sum it.

from collections import Counter

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        seen = Counter()
        bad = 0
        for j, x in enumerate(nums):
            key = x - j  # good partners share this value
            bad += j - seen[key]  # earlier indices that are not good partners
            seen[key] += 1
        return bad

What the code is doing, line by line:

1. j − i = nums[j] − nums[i] ⇔ nums[i] − i = nums[j] − j.
2. There are j earlier indices; those with the same key are good, the rest bad.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All good (arithmetic with step 1) → 0.
• All distinct keys → n(n − 1)/2.
• One element → 0.

Complexity: O(n) time and space.

Problem: For permutations A and B, C[i] = how many values appear in both A[:i+1] and B[:i+1].

Solve it on LeetCode ↗

Constraints: 1 ≤ A.length == B.length == n ≤ 50 · 1 ≤ A[i], B[i] ≤ n · It is guaranteed that A and B are both a permutation of n integers.

From brute force to the pattern: Set intersection per prefix is O(n²); counting is O(n).

Spot it: Each value appears once in each array; it's common from the index where its second occurrence (in either array) appears → a count array.

Why not another pattern? Intersecting the prefixes at every index is O(n²).

Approach:

1. seen[v] counts occurrences so far.
2. At index i, add A[i] and B[i]; each time a count reaches 2, common += 1.
3. C[i] = common.

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        seen = [0] * (len(A) + 1)
        common = 0
        C = []
        for a, b in zip(A, B):
            for v in (a, b):
                seen[v] += 1
                if seen[v] == 2:
                    common += 1  # now present in both prefixes
            C.append(common)
        return C

What the code is doing, line by line:

1. Values are a permutation, so each appears exactly once per array.
2. The second sighting means both prefixes contain it.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Same arrays → 1, 2, …, n.
• A[i] == B[i].
• n = 1.

Complexity: O(n) time and space.

Problem: You may swap characters whose indices differ by an even number, in either string. Can they be made equal?

Solve it on LeetCode ↗

Constraints: n == s1.length == s2.length · 1 ≤ n ≤ 10⁵ · s1 and s2 consist only of lowercase English letters.

From brute force to the pattern: Searching swap sequences is exponential; two counter comparisons are linear.

Spot it: Even-distance swaps never move a character between even and odd positions, and within each class any arrangement is reachable. So compare the letter counts of even positions and of odd positions.

Why not another pattern? Simulating swaps is unnecessary once the invariant is clear.

Approach:

1. Counter(s1[0::2]) == Counter(s2[0::2]).
2. Counter(s1[1::2]) == Counter(s2[1::2]).

from collections import Counter

class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        evens_match = Counter(s1[0::2]) == Counter(s2[0::2])  # characters at even indices
        odds_match = Counter(s1[1::2]) == Counter(s2[1::2])  # characters at odd indices
        return evens_match and odds_match

What the code is doing, line by line:

1. Parity of the position is preserved by every allowed swap.
2. Any permutation within a parity class is a product of allowed swaps.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Length 1.
• Same letters in the wrong parity.
• Already equal.

Complexity: O(n) time, O(1) space.

Problem: Map letters onto keys 2–9 freely. Minimise total pushes to type word (the k-th letter on a key costs k pushes).

Solve it on LeetCode ↗

Constraints: 1 ≤ word.length ≤ 10⁵ · word consists of lowercase English letters.

From brute force to the pattern: Trying letter-to-key assignments is factorial; greedy by frequency is O(n).

Spot it: Eight keys give 8 first slots, 8 second slots, …. Give the cheapest slots to the most frequent letters: count and sort descending.

Why not another pattern? Trying assignments is factorial; the exchange argument makes greedy optimal.

Approach:

1. Count letters; sort counts descending.
2. The i-th count (0-indexed) is multiplied by i // 8 + 1.

from collections import Counter

class Solution:
    def minimumPushes(self, word: str) -> int:
        counts = sorted(Counter(word).values(), reverse=True)  # most frequent first
        return sum(c * (i // 8 + 1) for i, c in enumerate(counts))  # 8 letters per push level

What the code is doing, line by line:

1. Swapping a more frequent letter into a cheaper slot never increases the total, so sorted order is optimal.
2. Positions 0–7 cost 1, 8–15 cost 2, and so on.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• ≤ 8 distinct letters → length of word.
• 26 distinct letters.
• One letter repeated.

Complexity: O(n) time, O(1) space.

Problem: Pick the largest subset arrangeable as [x, x², x⁴, …, xᵏ, …, x⁴, x², x].

Solve it on LeetCode ↗

Constraints: 2 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Subset enumeration is exponential; climbing square chains from each value is near-linear.

Spot it: Every level except the top needs two copies, the top needs one. With a counter, climb from each base value by squaring; 1 is special (1² = 1) and needs an odd count.

Why not another pattern? Trying subsets is exponential; values grow by squaring, so each chain has at most ~5 steps.

Approach:

1. Ones: use the largest odd number ≤ count[1].
2. For each x > 1: length = 0; while count[x] ≥ 2: length += 2, x = x².
3. Then +1 if x is present (top), else −1 (the last pair's one copy becomes the top).

from collections import Counter

class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        count = Counter(nums)
        ones = count[1]
        best = ones if ones % 2 else ones - 1  # a pattern of 1s needs an odd count
        for x in count:
            if x == 1:
                continue
            length = 0
            while count[x] >= 2:
                length += 2  # x on both sides
                x = x * x
            length += 1 if count[x] >= 1 else -1  # top of the pattern, or reuse the last pair's copy
            best = max(best, length)
        return best

What the code is doing, line by line:

1. Each level other than the peak appears twice in the pattern.
2. If the next square is missing, one copy of the last level becomes the peak (−1).
3. Squaring grows fast, so each chain is short (at most about 5 levels).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Many 1s (odd count).
• No pair anywhere → 1.
• Long chains like 2, 4, 16, 256.

Complexity: O(n log log V) time, O(n) space.

Problem: A letter is special if it appears in both cases and every lowercase occurrence comes before the first uppercase one.

Solve it on LeetCode ↗

Constraints: 1 ≤ word.length ≤ 2 * 10⁵ · word consists of only lowercase and uppercase English letters.

From brute force to the pattern: Comparing every lowercase/uppercase pair is O(n²); two maps are O(n).

Spot it: Only two positions per letter matter: the last lowercase and the first uppercase. Store them in hash maps in one pass.

Why not another pattern? Checking each pair of occurrences is O(n²).

Approach:

1. One pass: update last_lower[c] and set first_upper[c] once.
2. Count letters present in both with last_lower < first_upper.

class Solution:
    def numberOfSpecialChars(self, word: str) -> int:
        last_lower = {}
        first_upper = {}
        for i, ch in enumerate(word):
            if ch.islower():
                last_lower[ch] = i  # keeps the latest one
            else:
                first_upper.setdefault(ch.lower(), i)  # keeps the earliest one
        return sum(1 for c in last_lower if c in first_upper and last_lower[c] < first_upper[c])

What the code is doing, line by line:

1. If the last lowercase comes before the first uppercase, every lowercase does.
2. setdefault stores only the first uppercase index.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A lowercase after an uppercase → not special.
• Letters in one case only.
• Single character.

Complexity: O(n) time, O(1) space (26 letters).

Problem: Find three equal elements minimising |i − j| + |j − k| + |k − i|, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ n

From brute force to the pattern: All triples: O(n³). Grouped consecutive windows: O(n).

Spot it: For i < j < k the distance is 2(k − i), so only the outer two indices matter, and they should be as close as possible: three consecutive occurrences of the same value. Group positions with a hash map.

Why not another pattern? Trying all triples is O(n³).

Approach:

1. Group indices by value (in order).
2. For each group, check every window of three consecutive indices: 2 · (pos[t + 2] − pos[t]).

from collections import defaultdict

class Solution:
    def minimumDistance(self, nums: List[int]) -> int:
        where = defaultdict(list)  # value -> indices in increasing order
        for i, x in enumerate(nums):
            where[x].append(i)
        best = float("inf")
        for pos in where.values():
            for t in range(len(pos) - 2):
                best = min(best, 2 * (pos[t + 2] - pos[t]))  # tightest triple: consecutive occurrences
        return best if best < float("inf") else -1

What the code is doing, line by line:

1. |i − j| + |j − k| + |k − i| = 2(k − i) when i < j < k.
2. Skipping an occurrence between them only makes k − i larger, so consecutive triples are best.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No value appears three times → −1.
• Many copies of one value.
• Adjacent triple → 4.

Complexity: O(n) time and space.

Problem: Find i < j with reverse(nums[i]) == nums[j] minimising j − i, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: All pairs: O(n²). One pass with a map: O(n).

Spot it: For each j, the best partner is the latest earlier i whose reversed value equals nums[j]. A hash map from reversed value → latest index answers that in O(1).

Why not another pattern? Checking all pairs is O(n²).

Approach:

1. For each j: if nums[j] is in latest, update the best with j − latest[nums[j]].
2. Then store latest[reverse(nums[j])] = j.

class Solution:
    def minMirrorPairDistance(self, nums: List[int]) -> int:
        latest = {}  # reverse(nums[i]) -> the most recent such i
        best = float("inf")
        for j, x in enumerate(nums):
            if x in latest:
                best = min(best, j - latest[x])  # closest earlier mirror partner
            latest[int(str(x)[::-1])] = j  # leading zeros vanish in int()
        return best if best < float("inf") else -1

What the code is doing, line by line:

1. Looking up before inserting keeps i < j.
2. Overwriting with the latest index keeps the closest partner.
3. int("021") is 21, which drops leading zeros as required.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Trailing zeros (120 → 21).
• Palindromes pair with equal values.
• No pair → −1.

Complexity: O(n · digits) time, O(n) space.

Problem: Strings belong together if one can be shifted letter by letter (a→b→…→z→a) into the other. Group them (any order).

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ strings.length ≤ 200 · 1 ≤ strings[i].length ≤ 50 · strings[i] consists of lowercase English letters

From brute force to the pattern: Pairwise shift checks are quadratic; a canonical key groups in one pass.

Spot it: Shifting keeps the differences between neighbouring letters (mod 26). Use that tuple as a hash map key, like grouping anagrams.

Why not another pattern? Comparing every pair of strings by trying all 26 shifts is O(n² · L · 26).

Approach:

1. key(s) = tuple((ord(s[i]) − ord(s[i − 1])) % 26 for i ≥ 1).
2. Append each string to groups[key].
3. Return the groups.

from collections import defaultdict

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strings:
            key = tuple((ord(b) - ord(a)) % 26 for a, b in zip(s, s[1:]))  # shape that survives shifting
            groups[key].append(s)
        return list(groups.values())

What the code is doing, line by line:

1. Shifting every letter by the same amount leaves each neighbouring gap unchanged.
2. % 26 handles the wrap from z to a ("az" and "ba" both have gap 25).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single letters (all one group).
• Wrap-around (az, ba).
• Duplicates.

Complexity: O(total characters) time and space.

Problem: Rearrange s so its letters follow the order given in order (letters not in order can go anywhere).

Solve it on LeetCode ↗

Constraints: 1 ≤ order.length ≤ 26 · 1 ≤ s.length ≤ 200 · order and s consist of lowercase English letters. · All the characters of order are unique.

From brute force to the pattern: A key-based sort is O(n log n); counting is linear.

Spot it: Only counts matter: count s, write each letter of order as many times as it appears, then append the leftovers.

Why not another pattern? Sorting with a custom key works in O(n log n); counting is O(n).

Approach:

1. count = Counter(s).
2. For each letter in order: append it count[c] times and remove it.
3. Append the remaining letters.

from collections import Counter

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        count = Counter(s)
        out = []
        for ch in order:
            out.append(ch * count.pop(ch, 0))  # all copies, in the custom order
        for ch, k in count.items():
            out.append(ch * k)  # letters order doesn't mention
        return "".join(out)

What the code is doing, line by line:

1. pop removes letters already placed so they aren't repeated.
2. Any arrangement of the leftover letters is accepted.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Letters of order missing from s.
• Letters of s missing from order.
• Repeated letters.

Complexity: O(len(s) + len(order)) time, O(1) extra space (26 letters).

Problem: Design SparseVector(nums) with dotProduct(vec) that is efficient when most entries are zero.

Solve it on LeetCode ↗ (Premium)

Constraints: n == nums1.length == nums2.length · 1 ≤ n ≤ 10⁵ · 0 ≤ nums1[i], nums2[i] ≤ 100

From brute force to the pattern: The dense product is O(n); sparse pairs make it proportional to the number of non-zeros.

Spot it: Zeros contribute nothing, so store only non-zero (index, value) pairs. The dot product walks both sorted lists with two pointers, multiplying where indices match. (A hash map of index → value also works; pairs are what interviewers prefer when one vector is dense.)

Why not another pattern? Storing the whole array makes each product O(n) even when there are only a few non-zeros.

Approach:

1. Constructor: pairs = [(i, v) for v ≠ 0].
2. dotProduct: pointers a, b; equal indices → add the product and advance both; else advance the smaller index.

class SparseVector:
    def __init__(self, nums: List[int]):
        self.pairs = [(i, v) for i, v in enumerate(nums) if v]  # only non-zero entries, by index

    def dotProduct(self, vec: "SparseVector") -> int:
        a = b = 0
        total = 0
        x, y = self.pairs, vec.pairs
        while a < len(x) and b < len(y):
            if x[a][0] == y[b][0]:
                total += x[a][1] * y[b][1]  # both non-zero at this index
                a += 1
                b += 1
            elif x[a][0] < y[b][0]:
                a += 1  # the other vector is zero here
            else:
                b += 1
        return total

What the code is doing, line by line:

1. Only indices where both vectors are non-zero add to the product.
2. Both pair lists are sorted by index, so a merge-style walk finds the matches.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All zeros → 0.
• No overlapping non-zero indices.
• One dense and one sparse vector.

Complexity: O(n) to build, O(k₁ + k₂) per product for k non-zeros each.

Problem: A subarray is balanced if it has one distinct value, or every distinct value occurs f or 2f times with both frequencies present. Return the longest balanced subarray.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10³ · 1 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Counting each subarray from scratch is O(n³); incremental counts make it O(n²).

Spot it: n ≤ 1000 allows checking all O(n²) subarrays, if each check is O(1). Extend the end one step at a time, keeping a count map and a count-of-counts map: the subarray is balanced when the count-of-counts has one key (and one distinct value) or exactly two keys f and 2f.

Why not another pattern? Recounting each subarray from scratch is O(n³).

Approach:

1. For each start l: empty count and freq_of (count → how many values have it).
2. Add nums[r]: move that value from freq_of[c] to freq_of[c + 1] (deleting empty keys).
3. Balanced if len(count) == 1, or freq_of has two keys with the larger exactly twice the smaller.

from collections import defaultdict

class Solution:
    def getLength(self, nums: List[int]) -> int:
        best = 0
        for l in range(len(nums)):
            count = defaultdict(int)  # value -> occurrences in nums[l..r]
            freq_of = defaultdict(int)  # occurrences -> how many values have that many
            for r in range(l, len(nums)):
                c = count[nums[r]]
                if c:
                    freq_of[c] -= 1
                    if freq_of[c] == 0:
                        del freq_of[c]
                count[nums[r]] = c + 1
                freq_of[c + 1] += 1
                if len(count) == 1:
                    best = max(best, r - l + 1)  # one distinct value
                elif len(freq_of) == 2:
                    low, high = sorted(freq_of)
                    if high == 2 * low:
                        best = max(best, r - l + 1)  # every value occurs f or 2f times
        return best

What the code is doing, line by line:

1. The count-of-counts map always has at most a few keys, so each check is O(1).
2. Empty frequency keys are deleted so len(freq_of) is the number of distinct frequencies.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal → n.
• All distinct → 1.
• Frequencies f and 3f (not balanced).

Complexity: O(n²) time, O(n) space.

Problem: A pattern is 3 websites visited in that order by a user (not necessarily consecutively). Return the pattern visited by the most users (smallest lexicographically on ties).

Solve it on LeetCode ↗ (Premium)

Constraints: 3 ≤ username.length ≤ 50 · 1 ≤ username[i].length ≤ 10 · timestamp.length == username.length · 1 ≤ timestamp[i] ≤ 10⁹ · website.length == username.length · 1 ≤ website[i].length ≤ 10 · username[i] and website[i] consist of lowercase English letters · It is guaranteed that there is at least one user who visited at least three websites · All the tuples [username[i], timestamp[i], website[i]] are unique

From brute force to the pattern: This is the direct counting; the set per user is what prevents double counting.

Spot it: Sort each user's visits by time, generate every ordered triple of their visits, keep them in a set (a user counts once per pattern), then count patterns across users in a hash map.

Why not another pattern? Checking each candidate pattern against every user separately repeats work.

Approach:

1. Group (time, site) by user and sort by time.
2. For each user: set(combinations(sites, 3)).
3. Count over users; return min(count, key=(−count, pattern)).

from collections import Counter, defaultdict
from itertools import combinations

class Solution:
    def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
        visits = defaultdict(list)
        for t, user, site in sorted(zip(timestamp, username, website)):
            visits[user].append(site)  # in time order
        score = Counter()
        for sites in visits.values():
            for pattern in set(combinations(sites, 3)):  # each user counts a pattern once
                score[pattern] += 1
        best = min(score, key=lambda p: (-score[p], p))  # most users, then lexicographically smallest
        return list(best)

What the code is doing, line by line:

1. combinations keeps the visit order, which is what a pattern needs.
2. The set removes repeated patterns from the same user.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Users with fewer than 3 visits.
• Ties (lexicographic).
• Repeated sites in one user's history.

Complexity: O(Σ v³) for v visits per user (v ≤ 50), O of the number of patterns in space.

Problem: Put balls into boxes: each box holds one value, and box sizes differ by at most 1. Return the fewest boxes.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Assignments are combinatorial; trying each box size over the distinct counts is fast.

Spot it: Only the counts per value matter (a hash map). Every box has s or s + 1 balls for some s ≤ min count. A count c fits iff it can be split into ceil(c / (s + 1)) boxes of size s or s + 1. Try s from the largest possible down; the first that fits gives the fewest boxes.

Why not another pattern? Trying arbitrary box assignments is combinatorial.

Approach:

1. counts of each value; m = min(counts).
2. For s = m … 1: boxes for c = ceil(c / (s + 1)); valid if boxes · s ≤ c for all counts.
3. Return the total boxes for the first valid s.

from collections import Counter

class Solution:
    def minGroupsForValidAssignment(self, balls: List[int]) -> int:
        counts = list(Counter(balls).values())
        for s in range(min(counts), 0, -1):  # boxes hold s or s + 1 balls
            total = 0
            for c in counts:
                boxes = -(-c // (s + 1))  # as few boxes as possible
                if boxes * s > c:
                    break  # c can't fill that many boxes with at least s each
                total += boxes
            else:
                return total  # every value fits: larger s means fewer boxes
        return len(balls)

What the code is doing, line by line:

1. With b boxes of size s or s + 1, a count c fits iff b·s ≤ c ≤ b·(s + 1); the smallest b is ceil(c / (s + 1)).
2. Larger box sizes never need more boxes, so the first valid s from the top is optimal.
3. s = 1 always works, so the loop returns.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All distinct → n boxes.
• One value.
• Counts that can't share a size except 1.

Complexity: O(n · m) in the worst case, much less in practice (Σ over distinct counts).

Problem: Change at most one element, then pick the longest arithmetic subarray.

Solve it on LeetCode ↗

Constraints: 4 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁵

From brute force to the pattern: Trying each change with each value is O(n²) or worse; run lengths make it O(n).

Spot it: Work on the differences. Without a change, the answer is the longest run of equal differences + 1. A change either extends a run by one element at its border, or replaces an interior nums[i] so both neighbouring differences become c = (nums[i+1] − nums[i−1]) / 2, joining the equal-c runs on both sides.

Why not another pattern? Trying every change and value is O(n²) or worse.

Approach:

1. d[i] = nums[i+1] − nums[i]; end_run[i] / start_run[i] = length of the equal-difference run ending / starting at d[i].
2. Extend: min(n, longest run + 2) elements.
3. Bridge at interior i (when nums[i+1] − nums[i−1] is even): 3 + (end_run[i−2] if d[i−2] == c) + (start_run[i+1] if d[i+1] == c).

class Solution:
    def longestArithmetic(self, nums: List[int]) -> int:
        n = len(nums)
        d = [nums[i + 1] - nums[i] for i in range(n - 1)]
        m = len(d)
        end_run = [1] * m  # equal differences ending at d[i]
        for i in range(1, m):
            if d[i] == d[i - 1]:
                end_run[i] = end_run[i - 1] + 1
        start_run = [1] * m  # equal differences starting at d[i]
        for i in range(m - 2, -1, -1):
            if d[i] == d[i + 1]:
                start_run[i] = start_run[i + 1] + 1
        best = min(n, max(end_run) + 2)  # a run of k differences is k + 1 elements; change one neighbour to extend it
        for i in range(1, n - 1):  # change nums[i]
            gap = nums[i + 1] - nums[i - 1]
            if gap % 2:
                continue  # can't split an odd gap into two equal integer steps
            c = gap // 2
            length = 3  # nums[i-1], new nums[i], nums[i+1]
            if i - 2 >= 0 and d[i - 2] == c:
                length += end_run[i - 2]  # equal steps continue on the left
            if i + 1 < m and d[i + 1] == c:
                length += start_run[i + 1]  # and on the right
            best = max(best, length)
        return best

What the code is doing, line by line:

1. Changing an element right next to a run makes one more difference match, adding one element (never beyond n).
2. Changing an interior element affects exactly the two differences around it; their sum is fixed, so they can both equal c only if the gap is even.
3. The runs on each side then join through the changed element.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already arithmetic → n.
• Odd gaps (no bridge).
• Best change at an end.

Complexity: O(n) time and space.

Problem: You may replace nums[a] by nums[b] when nums[b] divides nums[a]. Minimise the array sum.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁵

From brute force to the pattern: All pairs: O(n²); a sieve over values: O(M log M).

Spot it: Replacements chain (divisibility is transitive), so each value can drop to the smallest value in the array that divides it. Find it for all values at once with a sieve: walk the distinct values from small to large and claim their multiples (a hash set of present values).

Why not another pattern? Checking every pair is O(n²).

Approach:

1. present = set of values; best[v] = v.
2. For each distinct d ascending: for multiples m of d ≤ max: if m is present and not yet claimed, best[m] = d.
3. Sum best[x] over the array.

class Solution:
    def minArraySum(self, nums: List[int]) -> int:
        present = set(nums)
        top = max(nums)
        best = {}  # value -> smallest present divisor
        for d in sorted(present):
            if d in best:
                continue  # its multiples are already claimed by a smaller divisor
            for m in range(d, top + 1, d):
                if m in present and m not in best:
                    best[m] = d
        return sum(best[x] for x in nums)

What the code is doing, line by line:

1. A value is replaced by any present divisor, and the smallest one gives the smallest sum.
2. If d was claimed by a smaller divisor e, every multiple of d is a multiple of e, so skipping d is safe.
3. The harmonic sum over divisors keeps the sieve near O(M log M).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No divisibility → unchanged.
• 1 present → everything becomes 1.
• Duplicates.

Complexity: O(M log M + n) time, O(M) space (M = max(nums)).

Problem: Return the maximum number of points that lie on one straight line.

Solve it on LeetCode ↗

Constraints: 1 ≤ points.length ≤ 300 · points[i].length == 2 · -10⁴ ≤ xi, yi ≤ 10⁴ · All the points are unique.

From brute force to the pattern: All triples: O(n³); slope counting per anchor: O(n²).

Spot it: Fix one point; every line through it is identified by its slope. Count points by slope in a hash map, with slopes stored as reduced integer pairs (gcd, fixed sign) to avoid floating-point errors.

Why not another pattern? Checking every triple of points is O(n³); float slopes can collide or differ wrongly.

Approach:

1. For each i: a counter of slopes to points j > i.
2. Slope key: (dy / g, dx / g) with g = gcd, normalised so dx > 0 (or dx = 0, dy = 1).
3. Best = 1 + the largest count.

from collections import Counter
from math import gcd

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        best = 1
        for i in range(n):
            slopes = Counter()
            x1, y1 = points[i]
            for j in range(i + 1, n):
                dx, dy = points[j][0] - x1, points[j][1] - y1
                g = gcd(dx, dy)
                dx, dy = dx // g, dy // g
                if dx < 0 or (dx == 0 and dy < 0):
                    dx, dy = -dx, -dy  # one canonical sign per direction
                slopes[(dx, dy)] += 1
            if slopes:
                best = max(best, 1 + max(slopes.values()))  # the anchor plus that line's points
        return best

What the code is doing, line by line:

1. Points are distinct, so g > 0.
2. Reduced integer pairs make equal slopes compare equal exactly.
3. Lines through earlier anchors were already counted when those anchors were processed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One point → 1.
• Vertical lines.
• Negative slopes.

Complexity: O(n² log C) time, O(n) space.

Problem: Use single planks or pairs glued end to end; all fence planks must have the same height. Return the maximum width.

Solve it on LeetCode ↗

Constraints: 1 ≤ planks.length ≤ 1000 · 1 ≤ planks[i] ≤ 10⁹

From brute force to the pattern: Trying every H and pairing greedily from scratch is O(n³); per-sum accumulation is O(D²).

Spot it: For a target height H, use every plank of height H, plus as many disjoint pairs (a, H − a) as possible: min(cnt[a], cnt[H − a]) per pair of values. Different a never compete for the same planks, so accumulate pair contributions per sum in a hash map over all value pairs.

Why not another pattern? Trying every height and recounting pairs from scratch is O(n³).

Approach:

1. cnt of heights; pairs[s] = planks usable as pairs summing to s.
2. For distinct values a < b: pairs[a + b] += min(cnt[a], cnt[b]); for each a: pairs[2a] += cnt[a] // 2.
3. Answer: max(cnt[H] + pairs[H]) over all H.

from collections import Counter

class Solution:
    def maximumWidth(self, planks: List[int]) -> int:
        cnt = Counter(planks)
        vals = sorted(cnt)
        pairs = Counter()  # height -> number of glued pairs that reach it
        for i, a in enumerate(vals):
            pairs[2 * a] += cnt[a] // 2  # two planks of the same height
            for b in vals[i + 1:]:
                pairs[a + b] += min(cnt[a], cnt[b])  # each pair uses one a and one b
        heights = set(cnt) | set(pairs)
        return max(cnt[h] + pairs[h] for h in heights)

What the code is doing, line by line:

1. A plank of height H can't be in a pair summing to H (heights are positive), so singles and pairs never conflict.
2. For a fixed H, each value a only pairs with H − a, so the pair counts for different values add up independently.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All planks equal.
• Only pairs reach the best height.
• One plank → 1.

Complexity: O(D²) time for D distinct heights (≤ 1000), O(D²) space.