18.7 maximum water trapped by vertical lines

#1

Line 3 within the Solution paragraph of this problem is:

The water trapped by the corresponding lines is (j-i)* min(A[j], A[i]), which can be done in O(n) time.

Is not this computation done in O(1) time for a given index pair (i, j)? I wasn’t sure why it says O(n) unless it’s counting multiplication as a not constant time operation.

1 Like

#2

Yes, this is actually an O(1) computation instead of O(n) computation. In our code, we actually use this O(n^2) implementation for testing the correctness of this algorithm.

0 Likes

#3

yes.

thanks for helpful clarification.

0 Likes