Island lake algorithm

Question 1

O(n) solution:

Go from left to right. Remember the first peak, find a higher peak (or a same height one), then draw a lake between them, than remember this higher peak and repeat the process. Then do the same going right to left. Its as simple as that. (Code is untested)

def island_lakes():
    lst=[]
    x=[int(i) for i in sys.stdin.readline().split()]
    lst.extend(x)

    print(lst)       

    cur_height = lst[0]
    valley_found = false
    for i in range(1, len(lst)):
        if lst[i] >= cur_height and valley_found:
            print(cur_height)
            valley_found = false
        else:
            valley_found = true

        if lst[i] >= cur_height:
            cur_height = lst[i]

    cur_height = lst[-1]
    valley_found = false
    for i in range(len(lst)-2, -1, -1):
        if lst[i] >= cur_height and valley_found:
            print(cur_height)
            valley_found = false
        else:
            valley_found = true

        if lst[i] >= cur_height:
            cur_height = lst[i]

Question 2

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.

Question 3

Asked a similar question and, of course, did not come up with this until later. My solution was easy to modify for this variant of the question. Key points:

Find the first peak starting at each end of the list.
The lower of the two peaks is gating peak regardless of what happens in the middle of the island.
Start working from the lower peak towards the middle.
Stop checking when the left peak and right peak meet (wherever that is).

There is a bit of extra bookkeeping to make sure the final list is in the right order (from left to right) and that it accounts for peaks that are flat spots (plateaus)

Each element in the list is only touched once, so this is O(n).

def lakeLevels(island):
  llist = []  # list of levels from the left side.
  rlist = []  # list of levels from the right side.

  lpeak = 0
  for i in range(1, len(island)):
    if island[i] < island[lpeak]:
      break
    else:
      lpeak = i

  rpeak = len(island)-1
  for i in range(len(island)-2, 0, -1):
    if island[i] < island[rpeak]:
      break
    else:
      rpeak = i

  while lpeak < rpeak:
    if island[lpeak] < island[rpeak]:
      i = lpeak+1
      # Following if check handles plateaus.
      if island[i] < island[lpeak]:
        llist.append(island[lpeak])

      while island[i] < island[lpeak]:
        i += 1
      lpeak = i

    else:
      i = rpeak-1
      # Following if check handles plateaus.
      if island[i] < island[rpeak]:
        rlist.insert(0,island[rpeak]) # Insert from the 
      while island[i] < island[rpeak]:
        i -= 1
      rpeak = i

  return llist + rlist

Question 4

I also have a solution for the problem, I have also added some comments in the code:

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] tokens = br.readLine().split(" ");
    int[] arr = new int[tokens.length];

    for (int i = 0; i < tokens.length; i++) {
        arr[i] = Integer.parseInt(tokens[i]);
    }

    Stack<Integer> stack = new Stack<Integer>();

    // biggestRight[i] stores the index of the element which is the greatest from the ones to the right of i
    int[] biggestRight = new int[tokens.length];

    // toRight[i] stores the first index to the right where the element is greater or equal to arr[i]
    int[] toRight = new int[tokens.length];
    int biggestIndex = -1;

    for (int i = arr.length - 1; i >= 0; i--) {
        biggestRight[i] = biggestIndex;

        if (biggestIndex == -1 || (biggestIndex != -1 && arr[i] >= arr[biggestIndex])) {
            biggestIndex = i;
        }
    }

    for (int i = arr.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            stack.pop();
        }

        if (stack.isEmpty()) {
            toRight[i] = -1;
        } else {
            toRight[i] = stack.peek();
        }

        stack.push(i);
    }

    System.out.println(Arrays.toString(biggestRight));
    System.out.println(Arrays.toString(toRight));

    /**
     * Iterate from left to right
     * When we are at arr[i]:
     *  (1) if toRight[i] != -1 -> this means that there is a possible valley starting at position i (we need to check the width of it)
     *  (2) if toRight[i] == -1 -> this means that we are at a peak and so we search for the biggest element to the right of i, because they constitute a valley
     *  (3) otherwise just move to the right by one
     */
    int i = 0;
    while (i < arr.length) {
        if (toRight[i] != -1 && toRight[i] > i + 1) {
            System.out.println(Math.min(arr[toRight[i]], arr[i]));
            i = toRight[i];
        } else if (toRight[i] == -1 && biggestRight[i] != -1 && biggestRight[i] > i + 1) {
            System.out.println(Math.min(arr[biggestRight[i]], arr[i]));
            i = biggestRight[i];
        } else {
            i++;
        }
    }
}