Map Sum Pairs

🎯

Map Sum Pairs

mediumTRIEGoogleAmazon

Imagine you are building a search autocomplete system that not only stores words but also keeps track of their associated scores, allowing quick retrieval of the sum of scores for all words sharing a prefix.

💡 This problem involves designing a data structure that supports dynamic insertion of key-value pairs and efficient prefix sum queries. Beginners often struggle because it requires combining trie data structure knowledge with maintaining aggregated sums, which is not straightforward at first.

📋

Problem Statement

Design a data structure that supports two operations: insert(key, val) - Inserts the key-value pair into the map. If the key already exists, the original key's value will be overridden to the new value. sum(prefix) - Returns the sum of all the values of keys that start with the given prefix.

1 ≤ key.length, prefix.length ≤ 50key and prefix consist of lowercase English letters1 ≤ val ≤ 10^5At most 10^4 calls will be made to insert and sum

💡

Example

Input"insert(\"apple\", 3), sum(\"ap\"), insert(\"app\", 2), sum(\"ap\")"

Outputnull, 3, null, 5

After inserting 'apple' with value 3, sum('ap') returns 3. Then inserting 'app' with value 2, sum('ap') returns 3 + 2 = 5.

• sum on prefix that does not exist → returns 0
• insert with key that already exists → updates value correctly
• insert empty string key (invalid input) → should be handled or ignored
• sum with empty prefix → returns sum of all keys

⚠️

Common Mistakes

Not updating prefix sums correctly on key update

Sum queries return incorrect totals due to stale sums

✅ Track old value and update sums by delta = new_val - old_val

Using hash map for children but forgetting to create nodes

Null pointer or key errors during sum traversal

✅ Always check and create child nodes when inserting new keys

Returning sum 0 when prefix is empty without considering all keys

Sum queries with empty prefix return 0 instead of total sum

✅ Root node sum stores total sum of all keys, so return root.sum for empty prefix

Using brute force approach in large input scenarios

Time limit exceeded due to scanning all keys on sum

✅ Use trie with prefix sums to achieve O(k) sum queries

🧠

Brute Force (Hash Map + Prefix Scan)

💡 This approach exists to establish a baseline understanding by using straightforward data structures without optimization. It helps beginners grasp the problem requirements before moving to complex tries.

Intuition

Store all key-value pairs in a hash map. For sum queries, iterate over all keys and accumulate values of keys starting with the prefix.

Algorithm

1. Initialize a hash map to store key-value pairs.
2. For insert(key, val), update or add the key with the given value.
3. For sum(prefix), iterate over all keys in the map.
4. Accumulate values of keys that start with the prefix and return the sum.

💡 The main challenge is realizing that sum queries require scanning all keys, which is inefficient but conceptually simple.

</>

Code

class MapSum:
    def __init__(self):
        self.map = {}

    def insert(self, key: str, val: int) -> None:
        self.map[key] = val

    def sum(self, prefix: str) -> int:
        total = 0
        for k, v in self.map.items():
            if k.startswith(prefix):
                total += v
        return total

# Driver code
if __name__ == "__main__":
    ms = MapSum()
    ms.insert("apple", 3)
    print(ms.sum("ap"))  # Output: 3
    ms.insert("app", 2)
    print(ms.sum("ap"))  # Output: 5

Line Notes

self.map = {}Initialize dictionary to store key-value pairs for direct access

self.map[key] = valInsert or update the key with the new value in O(1)

for k, v in self.map.items()Iterate over all stored keys to check prefix matches

if k.startswith(prefix)Check if current key matches the prefix to include in sum

import java.util.HashMap;

class MapSum {
    private HashMap<String, Integer> map;

    public MapSum() {
        map = new HashMap<>();
    }

    public void insert(String key, int val) {
        map.put(key, val);
    }

    public int sum(String prefix) {
        int total = 0;
        for (String k : map.keySet()) {
            if (k.startsWith(prefix)) {
                total += map.get(k);
            }
        }
        return total;
    }

    public static void main(String[] args) {
        MapSum ms = new MapSum();
        ms.insert("apple", 3);
        System.out.println(ms.sum("ap")); // 3
        ms.insert("app", 2);
        System.out.println(ms.sum("ap")); // 5
    }
}

Line Notes

map = new HashMap<>()Create a hash map to store key-value pairs efficiently

map.put(key, val)Insert or update the key with the given value in O(1)

for (String k : map.keySet())Iterate over all keys to find those matching the prefix

if (k.startsWith(prefix))Check prefix match to decide if value should be added

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

class MapSum {
    unordered_map<string, int> map;
public:
    void insert(string key, int val) {
        map[key] = val;
    }

    int sum(string prefix) {
        int total = 0;
        for (auto &p : map) {
            if (p.first.compare(0, prefix.size(), prefix) == 0) {
                total += p.second;
            }
        }
        return total;
    }
};

int main() {
    MapSum ms;
    ms.insert("apple", 3);
    cout << ms.sum("ap") << endl; // 3
    ms.insert("app", 2);
    cout << ms.sum("ap") << endl; // 5
    return 0;
}

Line Notes

unordered_map<string, int> map;Use hash map for O(1) insert and lookup

map[key] = val;Insert or update key's value directly

for (auto &p : map)Iterate over all key-value pairs to check prefix

p.first.compare(0, prefix.size(), prefix) == 0Check if key starts with prefix efficiently

class MapSum {
    constructor() {
        this.map = new Map();
    }

    insert(key, val) {
        this.map.set(key, val);
    }

    sum(prefix) {
        let total = 0;
        for (let [k, v] of this.map.entries()) {
            if (k.startsWith(prefix)) {
                total += v;
            }
        }
        return total;
    }
}

// Driver code
const ms = new MapSum();
ms.insert("apple", 3);
console.log(ms.sum("ap")); // 3
ms.insert("app", 2);
console.log(ms.sum("ap")); // 5

Line Notes

this.map = new Map();Initialize a Map object to store key-value pairs

this.map.set(key, val);Insert or update the key with the given value

for (let [k, v] of this.map.entries())Iterate over all entries to find prefix matches

if (k.startsWith(prefix))Check if the key starts with the prefix before adding

⏱

Complexity

TimeO(n * k) for sum queries, where n is number of keys and k is average key length

SpaceO(n * k) to store all keys and values

Insert is O(1) average due to hash map. Sum requires scanning all keys, each comparison O(k).

💡 For 10,000 keys each length 50, sum could do up to 500,000 character comparisons, which is slow.

Interview Verdict: TLE for large inputs

This approach is too slow for large datasets because sum queries scan all keys, so we need a better data structure.

🧠

Trie with Stored Prefix Sums

💡 This approach introduces a trie data structure to efficiently store prefixes and maintain cumulative sums, improving sum query speed significantly.

Intuition

Use a trie where each node stores the sum of all values of keys passing through it. On insert, update sums along the path. On sum, traverse prefix path and return stored sum.

Algorithm

1. Maintain a hash map to track existing keys and their values.
2. Build a trie where each node stores sum of values of keys passing through.
3. On insert, compute delta = new_val - old_val (0 if new key).
4. Traverse trie nodes for key, add delta to each node's sum.
5. On sum(prefix), traverse trie nodes for prefix and return node's sum or 0 if prefix not found.

💡 The key insight is updating prefix sums incrementally to avoid recomputing sums from scratch.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.sum = 0

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

    def insert(self, key: str, val: int) -> None:
        delta = val - self.map.get(key, 0)
        self.map[key] = val
        node = self.root
        node.sum += delta
        for ch in key:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.sum += delta

    def sum(self, prefix: str) -> int:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        return node.sum

# Driver code
if __name__ == "__main__":
    ms = MapSum()
    ms.insert("apple", 3)
    print(ms.sum("ap"))  # 3
    ms.insert("app", 2)
    print(ms.sum("ap"))  # 5

Line Notes

self.map = {}Track existing keys to compute delta on insert

delta = val - self.map.get(key, 0)Calculate difference to update prefix sums correctly

node.sum += deltaUpdate sum at root and each node along key path

if ch not in node.childrenCreate new trie nodes as needed for new characters

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    int sum = 0;
}

public class MapSum {
    private TrieNode root;
    private Map<String, Integer> map;

    public MapSum() {
        root = new TrieNode();
        map = new HashMap<>();
    }

    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode node = root;
        node.sum += delta;
        for (char ch : key.toCharArray()) {
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
            node.sum += delta;
        }
    }

    public int sum(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return 0;
            }
            node = node.children.get(ch);
        }
        return node.sum;
    }

    public static void main(String[] args) {
        MapSum ms = new MapSum();
        ms.insert("apple", 3);
        System.out.println(ms.sum("ap")); // 3
        ms.insert("app", 2);
        System.out.println(ms.sum("ap")); // 5
    }
}

Line Notes

map = new HashMap<>()Store keys and their values to compute delta on insert

int delta = val - map.getOrDefault(key, 0)Calculate difference between new and old value

node.children.putIfAbsent(ch, new TrieNode())Create child node if it doesn't exist

node.sum += deltaUpdate sum at each node along the key path

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    int sum = 0;
};

class MapSum {
    TrieNode* root;
    unordered_map<string, int> map;
public:
    MapSum() {
        root = new TrieNode();
    }

    void insert(string key, int val) {
        int delta = val - map[key];
        map[key] = val;
        TrieNode* node = root;
        node->sum += delta;
        for (char ch : key) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
            node->sum += delta;
        }
    }

    int sum(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            if (node->children.find(ch) == node->children.end()) {
                return 0;
            }
            node = node->children[ch];
        }
        return node->sum;
    }
};

int main() {
    MapSum ms;
    ms.insert("apple", 3);
    cout << ms.sum("ap") << endl; // 3
    ms.insert("app", 2);
    cout << ms.sum("ap") << endl; // 5
    return 0;
}

Line Notes

unordered_map<string, int> map;Track keys and values for delta calculation

int delta = val - map[key];Compute difference between new and old value

if (node->children.find(ch) == node->children.end())Create new trie node if missing

node->sum += delta;Update sum at each node along the key path

class TrieNode {
    constructor() {
        this.children = new Map();
        this.sum = 0;
    }
}

class MapSum {
    constructor() {
        this.root = new TrieNode();
        this.map = new Map();
    }

    insert(key, val) {
        const delta = val - (this.map.get(key) || 0);
        this.map.set(key, val);
        let node = this.root;
        node.sum += delta;
        for (const ch of key) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
            node.sum += delta;
        }
    }

    sum(prefix) {
        let node = this.root;
        for (const ch of prefix) {
            if (!node.children.has(ch)) {
                return 0;
            }
            node = node.children.get(ch);
        }
        return node.sum;
    }
}

// Driver code
const ms = new MapSum();
ms.insert("apple", 3);
console.log(ms.sum("ap")); // 3
ms.insert("app", 2);
console.log(ms.sum("ap")); // 5

Line Notes

this.map = new Map();Store keys and values to compute delta on insert

const delta = val - (this.map.get(key) || 0);Calculate difference between new and old value

if (!node.children.has(ch))Create new trie node if character path missing

node.sum += delta;Update sum at each node along the key path

⏱

Complexity

TimeO(k) per insert and sum, where k is length of key or prefix

SpaceO(n * k) for trie nodes and map storage

Insert and sum only traverse trie nodes along key or prefix, avoiding scanning all keys.

💡 For keys of length 50, each operation takes at most 50 steps, much faster than scanning all keys.

Interview Verdict: Accepted

This approach is efficient and suitable for large inputs, making it the preferred solution in interviews.

🧠

Trie with Array Children Optimization

💡 This approach optimizes the trie by using fixed-size arrays for children instead of hash maps, improving constant factors in runtime.

Intuition

Since keys contain only lowercase letters, use an array of size 26 for children nodes to speed up access and reduce overhead.

Algorithm

1. Use a trie node with an array of size 26 for children and an integer sum.
2. Maintain a map for key-value pairs to compute delta on insert.
3. On insert, update sums along the path using array indices for characters.
4. On sum, traverse prefix path using array indices and return sum or 0 if missing.

💡 This approach trades some memory for faster access by avoiding hash map overhead.

</>

Code

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

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

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

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

# Driver code
if __name__ == "__main__":
    ms = MapSum()
    ms.insert("apple", 3)
    print(ms.sum("ap"))  # 3
    ms.insert("app", 2)
    print(ms.sum("ap"))  # 5

Line Notes

self.children = [None]*26Preallocate fixed-size array for children to speed up access

idx = ord(ch) - ord('a')Convert character to array index for O(1) access

if not node.children[idx]Create new node if child does not exist at index

node.sum += deltaUpdate sum at each node along the key path

public class MapSum {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int sum = 0;
    }

    private TrieNode root;
    private Map<String, Integer> map;

    public MapSum() {
        root = new TrieNode();
        map = new HashMap<>();
    }

    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode node = root;
        node.sum += delta;
        for (char ch : key.toCharArray()) {
            int idx = ch - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
            node.sum += delta;
        }
    }

    public int sum(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            int idx = ch - 'a';
            if (node.children[idx] == null) {
                return 0;
            }
            node = node.children[idx];
        }
        return node.sum;
    }

    public static void main(String[] args) {
        MapSum ms = new MapSum();
        ms.insert("apple", 3);
        System.out.println(ms.sum("ap")); // 3
        ms.insert("app", 2);
        System.out.println(ms.sum("ap")); // 5
    }
}

Line Notes

TrieNode[] children = new TrieNode[26];Use fixed array for children to optimize access speed

int idx = ch - 'a';Calculate index for character in children array

if (node.children[idx] == null)Create child node if missing at index

node.sum += delta;Update sum at each node along the key path

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    int sum = 0;
};

class MapSum {
    TrieNode* root;
    unordered_map<string, int> map;
public:
    MapSum() {
        root = new TrieNode();
    }

    void insert(string key, int val) {
        int delta = val - map[key];
        map[key] = val;
        TrieNode* node = root;
        node->sum += delta;
        for (char ch : key) {
            int idx = ch - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
            node->sum += delta;
        }
    }

    int sum(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (!node->children[idx]) {
                return 0;
            }
            node = node->children[idx];
        }
        return node->sum;
    }
};

int main() {
    MapSum ms;
    ms.insert("apple", 3);
    cout << ms.sum("ap") << endl; // 3
    ms.insert("app", 2);
    cout << ms.sum("ap") << endl; // 5
    return 0;
}

Line Notes

TrieNode* children[26] = {nullptr};Fixed-size array for children nodes to speed up access

int idx = ch - 'a';Convert character to index for array access

if (!node->children[idx])Create new node if child does not exist at index

node->sum += delta;Update sum at each node along the key path

class TrieNode {
    constructor() {
        this.children = new Array(26).fill(null);
        this.sum = 0;
    }
}

class MapSum {
    constructor() {
        this.root = new TrieNode();
        this.map = new Map();
    }

    insert(key, val) {
        const delta = val - (this.map.get(key) || 0);
        this.map.set(key, val);
        let node = this.root;
        node.sum += delta;
        for (const ch of key) {
            const idx = ch.charCodeAt(0) - 97;
            if (!node.children[idx]) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
            node.sum += delta;
        }
    }

    sum(prefix) {
        let node = this.root;
        for (const ch of prefix) {
            const idx = ch.charCodeAt(0) - 97;
            if (!node.children[idx]) {
                return 0;
            }
            node = node.children[idx];
        }
        return node.sum;
    }
}

// Driver code
const ms = new MapSum();
ms.insert("apple", 3);
console.log(ms.sum("ap")); // 3
ms.insert("app", 2);
console.log(ms.sum("ap")); // 5

Line Notes

this.children = new Array(26).fill(null);Preallocate fixed-size array for children nodes

const idx = ch.charCodeAt(0) - 97;Calculate index for character in children array

if (!node.children[idx])Create new node if child does not exist at index

node.sum += delta;Update sum at each node along the key path

⏱

Complexity

TimeO(k) per insert and sum, with faster constant factors due to array indexing

SpaceO(n * k) for trie nodes and map storage

Array children reduce overhead compared to hash maps, improving runtime constants.

💡 This is a practical optimization that can make a difference in tight time constraints.

Interview Verdict: Accepted with better performance

This is the optimal practical implementation for interviews when keys are lowercase letters.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the trie with prefix sums approach (Approach 2 or 3) as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * k) per sum	O(n * k)	No	N/A	Mention only - never code
2. Trie with Hash Map Children	O(k) per insert and sum	O(n * k)	No	Yes	Code this for clarity and efficiency
3. Trie with Array Children	O(k) per insert and sum with better constants	O(n * k)	No	Yes	Code if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Present brute force approach using a hash map and prefix scan.Step 3: Explain inefficiency and motivate trie with prefix sums.Step 4: Implement trie with hash map children and prefix sums.Step 5: Discuss optimization using array children for lowercase letters.Step 6: Test code with examples and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Understanding of tries, ability to optimize data structures, handling updates and prefix queries efficiently, and clean code implementation.

Common Follow-ups

• How to handle deletions? → Update prefix sums by subtracting old value.
• What if keys contain uppercase or digits? → Use hash map children or larger arrays.

💡 Follow-ups test your ability to adapt the data structure to variations and maintain correctness.

🔍

Pattern Recognition

When to Use

1) Need to store key-value pairs with prefix queries, 2) Keys are strings, 3) Frequent prefix sum queries, 4) Updates to keys possible

Signature Phrases

sum of all keys that start withinsert key-value pairprefix sum query

NOT This Pattern When

Problems that only require exact key lookup or suffix queries are different patterns.

Similar Problems

Implement Trie (Prefix Tree) - basic trie constructionDesign Add and Search Words Data Structure - trie with wildcard searchMaximum XOR of Two Numbers in an Array - bit trie for numeric prefixes

Practice

1. Given the following code snippet for finding the longest word in a dictionary, what is the value of the variable longest after processing the input ["a", "app", "ap", "apply"]?

easy

A. "apply"

B. "app"

C. "ap"

D. "a"

Solution

1. Step 1: Insert words into trie

   Words "a", "app", "ap", "apply" are inserted. Only nodes with complete words have word attribute set.

2. Step 2: BFS traversal and update longest

   Traversal visits "a" first, then "ap", then "app". "apply" is not valid because "appl" prefix is missing. The longest valid word found is "app".

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   "app" is longest word with all prefixes present [OK]

Hint: Check prefix presence during BFS to update longest [OK]

Common Mistakes:

• Assuming "apply" is valid without all prefixes
• Not updating longest correctly on equal length
• Skipping lex order in BFS children iteration

2. Given the following code snippet implementing the trie-based autocomplete, and the input products = ["mobile", "mouse", "moneypot"] and searchWord = "mo", what is the value of the variable result after processing the entire searchWord?

easy

A. [["mobile", "moneypot", "mouse"], ["moneypot", "mobile", "mouse"]]

B. [["mobile", "moneypot", "mouse"], ["mobile", "moneypot", "mouse"]]

C. [["mobile", "mouse", "moneypot"], ["mobile", "mouse", "moneypot"]]

D. [["mobile", "mouse", "moneypot"], ["mouse", "mobile", "moneypot"]]

Solution

1. Step 1: Sort products lexicographically

   Sorted products: ["mobile", "moneypot", "mouse"]

2. Step 2: Build trie and collect suggestions

   For prefix 'm': suggestions are ["mobile", "moneypot", "mouse"]. For prefix 'mo': same suggestions as all start with 'mo'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Result matches expected suggestions for prefixes 'm' and 'mo' [OK]

Hint: Sorted products determine suggestion order at each prefix [OK]

Common Mistakes:

• Mixing order of suggestions
• Off-by-one in prefix traversal
• Appending suggestions after node moves

3. Consider the following snippet from the optimal Trie + DFS solution for Word Search II. Given the board and words below, what is the final list of words found? Board: [['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v']] Words: ["oath", "pea", "eat", "rain"]

from typing import List

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def buildTrie(self, words):
        root = TrieNode()
        for w in words:
            node = root
            for c in w:
                if c not in node.children:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.word = w
        return root

    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        root = self.buildTrie(words)
        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r, c, node):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            char = board[r][c]
            if char == '#' or char not in node.children:
                return
            node = node.children[char]
            if node.word:
                result.append(node.word)
                node.word = None
            board[r][c] = '#'
            dfs(r+1, c, node)
            dfs(r-1, c, node)
            dfs(r, c+1, node)
            dfs(r, c-1, node)
            board[r][c] = char

        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)
        return result

easy

A. ["eat"]

B. ["pea", "rain"]

C. ["oath", "pea", "eat", "rain"]

D. ["oath", "eat"]

Solution

1. Step 1: Trace DFS starting at 'o' (0,0)

   "oath" is found by following o->a->t->h path on the board.

2. Step 2: Trace DFS starting at 'e' (1,0)

   "eat" is found by e->a->t path on the board.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   "pea" and "rain" cannot be formed on the board [OK]

Hint: Only words fully traceable on board are found [OK]

Common Mistakes:

• Including words not present on board
• Missing words found by DFS
• Not handling visited cells correctly

4. The following code attempts to count pairs with XOR less than a limit using a bitwise trie. Identify the line that contains a subtle bug that causes incorrect counts on some inputs.

medium

A. Line where node.count is incremented during insert

B. Line where the trie is not reset between queries causing accumulation

C. Line where result accumulates query(num, limit) before insert

D. Line where node is updated to node.children[bit] during insert

Solution

1. Step 1: Understand trie usage in counting pairs

   The trie accumulates counts of inserted numbers to query how many have XOR less than limit with current number.

2. Step 2: Identify the bug

   The code does not reset or clear the trie between different calls or test cases, causing counts to accumulate incorrectly if reused, leading to wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Not resetting trie causes stale counts to affect results [OK]

Hint: Trie must be fresh or cleared per independent query [OK]

Common Mistakes:

• Not resetting trie between test cases
• Incrementing count incorrectly
• Wrong bit traversal order

5. What is the time complexity of the optimal trie-based solution to replace words in a sentence, where m is the number of words in the sentence and k is the average length of each word, assuming the trie is already built from n root words with average length l?

medium

A. O(n * l + m * k) because building the trie takes O(n * l) and searching each word takes O(k)

B. O(m * k) because each word is searched character by character in the trie until a prefix is found or word ends

C. O(m * k * l) because for each word, the trie traversal depends on both word and root lengths

D. O(m * n * l) because each word is compared against all roots in the trie

Solution

1. Step 1: Identify trie construction cost

   Building the trie from n roots each of length l takes O(n * l) time.

2. Step 2: Identify search cost per word

   Searching each of the m words of length k in the trie takes O(k) time per word.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of build and search times matches O(n*l + m*k) [OK]

Hint: Trie build and search costs add up [OK]

Common Mistakes:

• Assuming O(m*n*l) like brute force
• Multiplying k and l unnecessarily