Mark As Completed Discussion

Complexity Analysis

We are iterating through the heights input array 3 times sequentially.

  1. While creating left[].
  2. While creating right[].
  3. While summing result.

So the time complexity of the algorithm is O(3n) = O(n) where n is the length of the input array height.

We are creating two new arrays of the same length as height. So the space complexity is also O(2n) = O(n).