LeetCode 677: Map Sum Pairs Solution

Master LeetCode problem 677 (Map Sum Pairs), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

677. Map Sum Pairs

Medium

Hash Table String Design Trie

Problem Explanation

Explanation:

To solve this problem, we can use a Trie data structure where each node represents a character in the keys. Each node will have a HashMap to store the children nodes along with the value associated with that key. When inserting a key-value pair, we traverse through the Trie, creating nodes as needed. When calculating the sum for a given prefix, we traverse down the Trie until the prefix is matched, and then we recursively calculate the sum of all values below that node.

Steps:

Implement the Trie data structure with nodes having a HashMap of children nodes and value associated with the key.
Implement the insert method to insert key-value pairs into the Trie.
Implement the sum method to calculate the sum of values for keys with a given prefix.

Time Complexity:

Insertion: O(N), where N is the length of the key.
Sum: O(M), where M is the number of nodes in the Trie below the prefix.

Space Complexity:

O(N), where N is the total number of characters in all keys.:

Solution Code

class TrieNode {
    Map<Character, TrieNode> children;
    int value;

    public TrieNode() {
        children = new HashMap<>();
        value = 0;
    }
}

class MapSum {
    TrieNode root;

    public MapSum() {
        root = new TrieNode();
    }

    public void insert(String key, int val) {
        TrieNode curr = root;
        for (char c : key.toCharArray()) {
            curr.children.putIfAbsent(c, new TrieNode());
            curr = curr.children.get(c);
        }
        curr.value = val;
    }

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

    private int dfs(TrieNode node) {
        int sum = node.value;
        for (char c : node.children.keySet()) {
            sum += dfs(node.children.get(c));
        }
        return sum;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 677 (Map Sum Pairs)?

This page provides optimized solutions for LeetCode problem 677 (Map Sum Pairs) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 677 (Map Sum Pairs)?

The time complexity for LeetCode 677 (Map Sum Pairs) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 677 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 677 in Java, C++, or Python.

Back to LeetCode Solutions