Originally the problem said the numbers will be in the range 1 to 2000. I see this has been lowered to 1000 now. I updated my code accordingly.
Use Python 3. Or if you insist on Python 2, use unichr instead of chr.

@kpark - same with [[10,1],[3,8],[6,1],[5,6],[5,4],[5,8],[9,7],[9,2],[9,3],[6,2]] - it says the answer is [6,2] which means 1 has 2 parens - 10 and 6, and 8 has 2 parents - 3 & 5.

@sha256pki Actually I don't know how to determine the time complexity on average, I just saw this conclusion on wikipedia....The worst case should be O(n), but I am not sure about the complexity on average.