# Map Sum

• I'm sorry, but why is "Every insert operation is O(K^2)" ?
Isn't it K? It's just iterating one character at a time, and `prefix += c` is O(1).

• @wavy
`prefix += c is O(1)`
No it isn't - Java string is immutable. On each concatenation a new string is created, copying character by character and then appending the new character `c`. Each concatenation is O(K) on average.

Edit: Same for the python example. I guess if the string is mutable (like in Ruby using `<<` operator) then the time complexity should be O(K)

• The Java code you provided in approach 3 has a class called TrieNode, which has an attribute "end" but I don't see any usage of it in your code. Why did you add it?

• @jwgoh said in Map Sum:

No it isn't - Java string is immutable. On each concatenation a new string is created, copying character by character and then appending the new character c. Each concatenation is O(K) on average.

Thanks for let me know. I think you are right, and we need to have test case for string length above 10000 to give TLE

• @kk636 It has been corrected. Thank you

• @awice Sorry. I don't see any change to the code.

• Nice explanation. Thank you!

• I have the same confusion as raised before: why in approach 2, insert operation is O(K^2)? Isn't it O(K)?

• @sschangi As explained earlier, adding a character to a string creates a new string. In the course of adding "a" + "b" + "c" + "d" incrementally, we've created intermediate strings "a", "ab", "abc", "abcd".

• Isn't using `cur = cur.children.setdefault(char, TrieNode())` in the 3rd python solution quite inefficient, since you construct a new `TrieNode` even if you don't need it?

• However, for the specific cases like if we use a StringBuilder for second solution in Java, the runtime can be optimized to O(K). As StringBuilder is essentially an ArrayList and the amortized runtime for insert is O(1)

• However, for the specific cases like if we use a StringBuilder for second solution in Java, the runtime can be optimized to O(K). As StringBuilder is essentially an ArrayList and the amortized runtime for insert is O(1)

• @amirshim In order to fully insert a key into the trie, we must have a node for every prefix of the key, making nodes if necessary.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.