In order to find the maximum altitude of the lakes that could potentially form, you need to find all of the peaks, or points that are higher than the points around them. Modifying your code a little bit, we can easily get the peaks in one iteration:
lst = [0] + lst + [0] # Add zeros to either side to avoid having to deal with boundary issues
peaks = []
for x in range(1, len(lst)-1):
if lst[x-1] =< lst[x] >= lst[x+1]: # "x =< y >= z" is the same as "x =< y and y >= z"
peaks.append(lst[x])
For your example of 4 3 7 1 3 2 3 5 6 2 1 3 3 2 3
, peaks would be
[4, 7, 3, 6, 3, 3, 3]
Now, we need to merge lakes. The way we find which lakes can be merged is to go through the list of peaks, keeping track of the highest peak so far, and for each peak we remove any previous peaks that are lower than it and the highest peak so far. However, this does not require any look-ahead information, so we can do this in the same for
loop as the one that finds the peaks in the first place:
highest_so_far = 0
for x in range(1, len(lst)-1):
if lst[x-1] =< lst[x] >= lst[x+1]: # "x =< y >= z" is the same as "x =< y and y >= z"
while peaks and highest_so_far > peaks[-1] < lst[x]:
peaks.pop()
if lst[x] > highest_so_far:
highest_so_far = lst[x]
peaks.append(lst[x])
This will reduce the peaks in our example to
[4, 7, 6, 3, 3, 3]
Now, to find all lakes, we simply go through the list and output the lower of each pair. However, there's a wrinkle - with the series of 3's, how do we know if it is flat ground or a lake separating peaks of equal height? We have to know if the points are adjacent to each other or not. That can be done by including position information along with each peak -
peaks.append((lst[x], x))
Then as we go through the final list of peaks, we check for the lower of the two, and if they are equal we check if they are next to each other (no lake if they are).
Just so that I'm not writing all the code for you, I'll leave it to you to modify the loop to work with peaks
containing tuples and to write the loop that determines the lakes based on the peaks found.
As for the time complexity, I believe this runs in linear time. Obviously, we only run through the list once, but there is the while
loop in the middle. At each iteration, the while loop will check at least one peak, but if it ever checks more than one peak it is because at least one peak has been removed. Thus, beyond the one-per-iteration check, no peak will be checked multiple times, giving at most a linear increase in time required.