educative.io

Educative

Cubic space complexity, how?

How this solution has cubic space complexity in the worst case? Shouldn’t be quadratic in the worst case? In cubic space complexity every subarray should have a subarray of the maximum of N elements which can newer happen in this example?

Hi @Mladen_Milosavljevic

The main for-loop managing the sliding window takes O(N) but creating subarrays can take up to O(N^2) in the worst case. Therefore overall, our algorithm will take O(N^3).

That’s time complexity, my question is related to space complexity.