Map Sum Pairs

▶

Steps

setup

Initialize MapSum and Trie Root

Create the MapSum object with an empty root TrieNode and an empty map for key-value pairs.

💡 Initialization sets up the data structures needed for insertions and prefix sum queries.

Line:

ms = MapSum()

💡 The root node starts with sum 0 and no children, ready to build the trie.

insert

Insert 'apple' with value 3: Update root sum

Calculate delta = 3 - 0 = 3 since 'apple' is new. Update root node sum by adding delta.

💡 Updating the root sum reflects that all keys passing through root contribute to sums.

Line:

delta = val - self.map.get(key, 0)
self.map[key] = val
node = self.root
node.sum += delta

💡 The root sum accumulates all inserted values, starting with the first insertion.

insert

Insert 'apple': Insert 'a' child and update sum

Check if root has child 'a'. It does not, so create new node for 'a'. Update sum of 'a' node by delta=3.

💡 Creating new nodes for characters extends the trie to represent the key.

Line:

idx = ord(ch) - ord('a')
if not node.children[idx]:
    node.children[idx] = TrieNode()
node = node.children[idx]
node.sum += delta

💡 New nodes are created only when needed, and sums are updated along the path.

insert

Insert 'apple': Insert 'p' child and update sum (first 'p')

At node 'a', check for child 'p'. Not found, create new node for 'p'. Update sum by delta=3.

💡 Continuing to build the path for 'apple' by adding next character nodes.

Line:

idx = ord(ch) - ord('a')
if not node.children[idx]:
    node.children[idx] = TrieNode()
node = node.children[idx]
node.sum += delta

💡 Each character extends the trie path and accumulates sums.

insert

Insert 'apple': Insert 'p' child and update sum (second 'p')

At node for first 'p', check for child 'p'. Not found, create new node for second 'p'. Update sum by delta=3.

💡 Handling repeated characters by creating separate nodes for each occurrence.

Line:

idx = ord(ch) - ord('a')
if not node.children[idx]:
    node.children[idx] = TrieNode()
node = node.children[idx]
node.sum += delta

💡 Trie nodes represent characters in sequence, even if repeated.

insert

Insert 'apple': Insert 'l' child and update sum

At second 'p' node, check for child 'l'. Not found, create new node for 'l'. Update sum by delta=3.

💡 Continuing to add nodes for the remaining characters of the key.

Line:

idx = ord(ch) - ord('a')
if not node.children[idx]:
    node.children[idx] = TrieNode()
node = node.children[idx]
node.sum += delta

💡 Each new character extends the trie path and updates sums.

insert

Insert 'apple': Insert 'e' child and update sum

At 'l' node, check for child 'e'. Not found, create new node for 'e'. Update sum by delta=3.

💡 Final character node is created to complete the key insertion.

Line:

idx = ord(ch) - ord('a')
if not node.children[idx]:
    node.children[idx] = TrieNode()
node = node.children[idx]
node.sum += delta

💡 The trie path now fully represents 'apple' with sums updated along the path.

sum

Sum 'ap': Traverse root to 'a' and update active path

Start sum query for prefix 'ap'. Begin at root and move to child 'a'.

💡 Traversing the trie along the prefix path locates the node whose sum is returned.

Line:

node = self.root
for ch in prefix:
    idx = ord(ch) - ord('a')
    if not node.children[idx]:
        return 0
    node = node.children[idx]

💡 Prefix traversal follows existing nodes to accumulate sums.

sum

Sum 'ap': Traverse to 'p' node and read sum

Continue traversal to child 'p' node. Node exists, so sum at 'p' node is returned as result.

💡 The sum stored at the last prefix node is the total value of all keys with that prefix.

Line:

node = node.children[idx]
return node.sum

💡 Sum query efficiently returns prefix sums without scanning all keys.

insert

Insert 'app' with value 2: Calculate delta and update root sum

Calculate delta = 2 - 0 = 2 since 'app' is new. Update root sum by adding delta=2.

💡 Delta calculation ensures sums reflect updated values for keys.

Line:

delta = val - self.map.get(key, 0)
self.map[key] = val
node = self.root
node.sum += delta

💡 Root sum now reflects total of all inserted keys: 3 + 2 = 5.

insert

Insert 'app': Traverse to 'a' and update sum

At root, move to child 'a' node and add delta=2 to its sum.

💡 Updating sums along existing paths accumulates values for all keys sharing prefixes.

Line:

idx = ord(ch) - ord('a')
node = node.children[idx]
node.sum += delta

💡 Sums at nodes reflect cumulative values of all keys passing through.

insert

Insert 'app': Traverse to first 'p' and update sum

At 'a' node, move to child 'p' node and add delta=2 to its sum.

💡 Continuing to update sums along the key's path.

Line:

idx = ord(ch) - ord('a')
node = node.children[idx]
node.sum += delta

💡 Sum updates propagate through all nodes representing the key.

insert

Insert 'app': Traverse to second 'p' and update sum

At first 'p' node, move to child second 'p' node and add delta=2 to its sum.

💡 Final node in key path updated to reflect new key's value.

Line:

idx = ord(ch) - ord('a')
node = node.children[idx]
node.sum += delta

💡 Sum at last character node reflects total values of keys ending or passing through.

sum

Sum 'ap': Traverse root to 'a' for sum query

Start sum query for prefix 'ap'. Move from root to child 'a'.

💡 Prefix traversal locates node to read sum from.

Line:

node = self.root
for ch in prefix:
    idx = ord(ch) - ord('a')
    if not node.children[idx]:
        return 0
    node = node.children[idx]

💡 Traversal follows prefix characters to find sum node.

sum

Sum 'ap': Traverse to 'p' node and read sum 5

Move to child 'p' node of 'a'. Node exists, return sum 5 as result for prefix 'ap'.

💡 Sum at node 'p' reflects total values of keys with prefix 'ap'.

Line:

node = node.children[idx]
return node.sum

💡 Sum query efficiently returns combined values of all keys sharing prefix.

class TrieNode:
    def __init__(self):
        self.children = [None]*26  # STEP 1
        self.sum = 0  # STEP 1

class MapSum:
    def __init__(self):
        self.root = TrieNode()  # STEP 1
        self.map = {}  # STEP 1

    def insert(self, key: str, val: int) -> None:
        delta = val - self.map.get(key, 0)  # STEP 2,10
        self.map[key] = val  # STEP 2,10
        node = self.root  # STEP 2,10
        node.sum += delta  # STEP 2,10
        for ch in key:  # STEP 3-7,11-13
            idx = ord(ch) - ord('a')  # STEP 3-7,11-13
            if not node.children[idx]:  # STEP 3-7
                node.children[idx] = TrieNode()  # STEP 3-7
            node = node.children[idx]  # STEP 3-7,11-13
            node.sum += delta  # STEP 3-7,11-13

    def sum(self, prefix: str) -> int:
        node = self.root  # STEP 8,14
        for ch in prefix:  # STEP 8,14
            idx = ord(ch) - ord('a')  # STEP 8,14
            if not node.children[idx]:  # STEP 8,14
                return 0  # STEP 8
            node = node.children[idx]  # STEP 8,14
        return node.sum  # STEP 9,15

if __name__ == "__main__":
    ms = MapSum()  # STEP 1
    ms.insert("apple", 3)  # STEP 2-7
    print(ms.sum("ap"))  # STEP 8-9
    ms.insert("app", 2)  # STEP 10-13
    print(ms.sum("ap"))  # STEP 14-15

📊

Map Sum Pairs - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the trie accumulates sums for prefixes, which is hard to grasp from code alone.

insert

insert

apple

insert

apple

a

insert

apple

ap

insert

apple

app

insert

apple

appl

insert

apple

apple

sum

ap

apple

sum

ap

apple

Search: true

insert

app

apple

insert

app

apple

insert

app

apple

insert

app

apple

sum

ap

apple

sum

ap

apple

Search: true

Key Takeaways

✓ Trie nodes store cumulative sums of all keys passing through, enabling efficient prefix sum queries.

This is hard to see from code alone because the sum updates happen incrementally along the path.

✓ Insertions update sums along existing paths without rebuilding the entire trie.

Watching the incremental sum updates clarifies how overlapping prefixes share nodes.

✓ Sum queries traverse only the prefix path and return the stored sum, avoiding scanning all keys.

This efficiency is clear when seeing traversal stop at prefix end and directly read sum.

Practice

1. Given the following Trie implementation, after inserting the words ['cat', 'car', 'dog'], what is the value of node.isEnd after processing the last character of 'car' in the insert method?

easy

A. false, because 'car' shares prefix with 'cat' and 'dog'

B. true, but only if 'car' was inserted before 'cat'

C. false, because isEnd is only set after inserting all words

D. true, because 'car' is a complete inserted word

Solution

1. Step 1: Trace insertion of 'car'

   For each character 'c', 'a', 'r', nodes are created or reused. After last character 'r', node.isEnd is set to true.

2. Step 2: Confirm isEnd flag meaning

   isEnd marks the end of a complete word. Since 'car' was inserted, node.isEnd after 'r' is true.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   isEnd is true after inserting 'car' [OK]

Hint: isEnd is set true after inserting each complete word [OK]

Common Mistakes:

• Assuming isEnd is false if prefix overlaps with other words

2. Consider the following Python code implementing the optimal StreamChecker. Given the words ["cd", "f", "kl"], what is the return value of the query sequence: query('a'), query('b'), query('c'), query('d')? Specifically, what does query('d') return?

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

class StreamChecker:
    def __init__(self, words):
        self.root = TrieNode()
        self.max_len = max(len(w) for w in words)
        self.stream = []
        for word in words:
            node = self.root
            for ch in reversed(word):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_word = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True
        return False

sc = StreamChecker(["cd", "f", "kl"])
print(sc.query('a'))
print(sc.query('b'))
print(sc.query('c'))
print(sc.query('d'))

easy

A. False

B. True

C. Raises an exception

D. None

Solution

1. Step 1: Trace the stream buffer after queries

   After queries 'a', 'b', 'c', 'd', the stream buffer contains ['a','b','c','d'], but max_len=2, so oldest letters are popped. After 'c', stream=['b','c'], after 'd', stream=['c','d'].

2. Step 2: Traverse trie with reversed stream

   For query('d'), reversed stream is ['d','c']. Trie has reversed words: 'dc' for 'cd'. Traversing 'd' then 'c' hits is_word=True at 'c' node, so returns True. However, the query sequence is query('a'), query('b'), query('c'), query('d'). The query('c') returns False because 'c' alone is not a word. The query('d') returns True because 'cd' is in the dictionary and the stream buffer contains ['c','d'].

3. Step 3: Check query('d') return value

   Since the query('d') returns True, the correct answer is True.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stream buffer limited to max word length matches 'cd' suffix [OK]

Hint: Stream buffer limited to max word length [OK]

Common Mistakes:

• Not limiting stream buffer size
• Not reversing words in trie
• Returning false too early

3. What is the time complexity of the optimal bitwise trie approach to count pairs with XOR in a range for an input array of size n and maximum number M (max element)?

medium

A. O(n * log M)

B. O(n^2)

C. O(n * M)

D. O(n * log n)

Solution

1. Step 1: Identify operations per element

   Each number is inserted into the trie in O(log M) time, where M is the max number (bit length).

2. Step 2: Query per element also takes O(log M)

   For each number, querying the trie for counts less than a limit also takes O(log M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n * log M) due to insert and query per element [OK]

Hint: Trie operations scale with bit length, not array size squared [OK]

Common Mistakes:

• Assuming O(n^2) due to pairs
• Confusing M with n in complexity
• Ignoring log factor from bit length

4. What is the time complexity of the optimal bitwise trie approach to find the maximum XOR of two numbers in an array of size n, assuming 32-bit integers?

medium

A. O(n^2)

B. O(n * log n)

C. O(32^2 * n)

D. O(n * 32)

Solution

1. Step 1: Identify loops in the algorithm

   We insert each of the n numbers into the trie, iterating over 32 bits each time -> O(n * 32).

2. Step 2: Find max XOR by traversing trie for each number

   Again, for each number, we traverse 32 bits -> O(n * 32).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   32 is constant, so complexity is linear in n times 32 bits [OK]

Hint: Each number processed over fixed 32 bits [OK]

Common Mistakes:

• Mistaking complexity as O(n^2) due to pairwise XOR

5. What is the time complexity of processing Q queries using the optimal StreamChecker approach that builds a trie of reversed words and maintains a stream buffer limited to the maximum word length L? Assume W words with maximum length L. Choose the most accurate complexity.

medium

A. O(Q * W * L)

B. O(Q * L^2)

C. O(Q * L)

D. O(Q + W * L)

Solution

1. Step 1: Identify operations per query

   Each query appends a letter and traverses at most L nodes in the trie (limited by max word length).

2. Step 2: Calculate total complexity

   Building the trie takes O(W * L) once. Each query takes O(L) time. Total is O(Q * L) for queries plus O(W * L) for setup, dominated by O(Q * L) for large Q.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Traversal limited to max word length L per query [OK]

Hint: Traversal limited to max word length L per query [OK]

Common Mistakes:

• Confusing brute force O(Q*W*L) with trie approach
• Assuming quadratic in L
• Ignoring trie build cost