1. I provide not the optimal solution for the first task by using more memory than necessary. Time - O(n), Memory O(n) where n is the maximum value in the array. My proposal about improvement related to BST was not clear and make some mess in conversation. 2. I was not able to improve my solution to thread-safe (but have some proposal on how it can be implemented).