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?
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.