educative.io

Educative

Space complexity analysis for sliding window and two pointer

I finished the section for sliding window and am about halfway through two pointer. Those are very helpful and organized collection. It helps by organizing similar questions together and it is easy to find the similarity between them and generalize to interviews. I think this is more helpful than just solving questions on leetcode. It gives a more organized manner.

However, I couldnt help but notice that many space complexity analysis is simply wrong for a lot of these questions. The use of unordered_map for sliding window is O(1) space complexity, since the size of map is <=26, the length of alphabet. Also, the space complexity for sorting should also be O(1), not O(n).