If you use map, the solution is not O(n^2)

  • -2

    Most of the solutions posted using map claimed an O(N^2) algorithm, because they assume finding a key in a map takes constant time. Clearly, it may not be the case.

  • 0

    Would be good if you explained a bit instead of just claiming "clearly".

  • 0

    amortized key look-up in a hashmap in Java is O(1) time, even though the buckets can contain LinkedLists or Red-Black Trees. Please, explain your logic otherwise.

Log in to reply

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