Map Sum Pairs - Practice Coding Problems

Map Sum Pairs - Problem

Design a map that allows you to do the following:

Maps a string key to a given value
Returns the sum of the values that have a key with a prefix equal to a given string

Implement the MapSum class:

MapSum() Initializes the MapSum object
void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-value pair will be overridden to the new one
int sum(string prefix) Returns the sum of all the pairs' value whose key starts with the prefix

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["MapSum", "insert", "sum", "insert", "sum"], values = [[], ["apple",3], ["ap"], ["app",2], ["ap"]]

› Output: [null, null, 3, null, 5]

💡 Note: MapSum() creates object, insert("apple",3) adds key, sum("ap") returns 3, insert("app",2) adds another key, sum("ap") returns 3+2=5

Example 2 — Key Override

$ Input: operations = ["MapSum", "insert", "sum", "insert", "sum"], values = [[], ["apple",3], ["app"], ["apple",2], ["app"]]

› Output: [null, null, 3, null, 2]

💡 Note: After inserting apple=3, sum("app") returns 3. After updating apple=2, sum("app") returns 2 (original value overridden)

Example 3 — No Matching Prefix

$ Input: operations = ["MapSum", "insert", "sum", "sum"], values = [[], ["apple",3], ["app"], ["xyz"]]

› Output: [null, null, 3, 0]

💡 Note: sum("app") finds "apple" with prefix match, returns 3. sum("xyz") finds no keys with this prefix, returns 0

Constraints

1 ≤ key.length, prefix.length ≤ 50
key and prefix consist of only lowercase English letters
1 ≤ val ≤ 1000
At most 50 calls will be made to insert and sum

Visualization

Tap to expand

Understanding the Visualization

Input

Operations: insert keys with values, query prefix sums

Process

Build trie storing cumulative sums at each node

Output

Fast O(prefix length) sum queries

Key Takeaway

🎯 Key Insight: Trie nodes can store aggregate sums for instant prefix queries

Asked in

G Google 45 a Amazon 35 M Microsoft 25

Brief HTML summary: The key insight is using a trie data structure where each node stores the sum of all values in its subtree. Best approach is the trie with prefix sums for O(m) query time where m is prefix length. Time: O(m), Space: O(ALPHABET_SIZE × N × M)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Hash Map	O(n)	O(n)	Store key-value pairs in hash map, scan all keys for each prefix query
Optimized Trie with Prefix Sums	O(m)	O(ALPHABET_SIZE × N × M)	Use trie data structure where each node stores sum of all values in its subtree

Brute Force with Hash Map — Algorithm Steps

Store all key-value pairs in hash map
For sum query, iterate all keys
Check if each key starts with prefix
Sum values of matching keys

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Keys

Insert keys into hash map

Linear Search

Check each key for prefix match

Sum Values

Add values of matching keys

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_KEYS 1000
#define MAX_LEN 100

typedef struct {
    char keys[MAX_KEYS][MAX_LEN];
    int values[MAX_KEYS];
    int size;
} MapSum;

MapSum* mapSumCreate() {
    MapSum* obj = (MapSum*)malloc(sizeof(MapSum));
    obj->size = 0;
    return obj;
}

void mapSumInsert(MapSum* obj, char* key, int val) {
    for (int i = 0; i < obj->size; i++) {
        if (strcmp(obj->keys[i], key) == 0) {
            obj->values[i] = val;
            return;
        }
    }
    strcpy(obj->keys[obj->size], key);
    obj->values[obj->size] = val;
    obj->size++;
}

int mapSumSum(MapSum* obj, char* prefix) {
    int total = 0;
    int prefixLen = strlen(prefix);
    for (int i = 0; i < obj->size; i++) {
        if (strncmp(obj->keys[i], prefix, prefixLen) == 0) {
            total += obj->values[i];
        }
    }
    return total;
}

int main() {
    // Implementation simplified for this example
    printf("[null,null,3,null,2]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each sum query scans all n stored keys

✓ Linear Growth

Space Complexity

O(n)

Hash map stores n key-value pairs

⚡ Linearithmic Space

38.0K Views

Medium Frequency

~25 min Avg. Time

950 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler