search

jaideeppyne / leetcode-problem-solving

Started solving 30 days May challenge on Leetcode. It provides one question daily at 12:30pm IST with 24hours deadline to solve. This challenge occurs monthly.
0 stars 0 forks source link

Wrong complexity for Create Insert Delete GetRandom O(1) problem #15

Open jakobkogler opened 4 years ago

jakobkogler commented 4 years ago

The problem statement says, that all three operations should take O(1) time on average. However the current implementation is only O(n) on average. It might have passed the Leetcode submission, as their tests are usually not strong. But the code logic is technically still wrong...

Both the C++ and the Python versions are affected:

https://github.com/jaideeppyne/leetcode-problem-solving/blob/9329dc4864a3f3ba68ec48ed668bd6507e808d0c/June%20Challenge/CPP/Insert%20Delete%20GetRandom%20O(1)%20%20Solution#L56-L70

https://github.com/jaideeppyne/leetcode-problem-solving/blob/9329dc4864a3f3ba68ec48ed668bd6507e808d0c/June%20Challenge/Python/Insert%20Delete%20GetRandom%20O(1)%20Solution.py#L21-L34

harshraj22 commented 4 years ago

The python version is just implementation of c++ version and doesn't has its own exitence.