Map Sum Pairs | Leetcode 677 | Live coding session

Here is the solution to "Map Sum Pairs" leetcode question. Hope you have a great time going through it.

1) 0:00 Explaining the problem out loud
2) 1:10 Algorithm walkthrough
3) 2:30 Solution
4) 8:00 Coding and Time Complexity

PS : Please increase the speed to 1.25X

[AnshulVerma-cdod]

Geat explanation and Awesome playlist😀

[jaatharsh]

one can further improve the performance by instead of storing value in TrieNode u just store the reference to Dictionary/HashTable which also hold key-value mapping,
and now whenever we have an update or existing key we need not traverse the Trie but instead just update the Dictionary.

[saoravsaha]

The trie approach can be more simplified. We do not need to use the DFS part.
While adding the strings to the trie, there and then add the values to each of the characters. In this way we will have a prefix sum of all the character. At the time of retrieving just traverse till the prefix and return the Value of last character in prefix as it will have minimum among all character of prefix. If any node comes which does not exist then simply return zero as prefix does not exist in this case.

Example -
Cat - 5 -> so c-5, a-5, t-5
Then, car -7 -> c-5+7=12, a-5+7=12, r-5
Then cs -3 -> c-12+3=15, s-3 and so on..
Now for prefix ca -> c-15, a-12 lastValue 12 so return 12.