Island Lake Algorithm

Question

Summary

Suppose you have a mountain two-dimensional island. Because of how rainy it is, all the valleys on the island are completely filled with water, to the point that adding water will no longer overflow the lakes. If the overflow passes to another lake, it will also overflow. In the end, water will flow from the island. Given the shape of the island, how do you know which lakes are formed?

More details

Reading a sequence of numbers (each number representing the height of a point in a two-dimensional connected graph) calculates and displays the surface height of all the lakes that can form in the valleys of the island.

For example, input 4 3 7 1 3 2 3 5 6 2 1 3 3 2 3 (in the photo below) should give output 4 6 3 3 in time complexity of no more than O(n log n) .

What does the algorithm look like? Can this be done in linear complexity?

Here is the code that I still have:

 import sys def island_lakes(): lst=[] lst1=[0]*3 x=[int(i) for i in sys.stdin.readline().split()] lst.extend(x) print(lst) for x in range(len(lst)-1): if x>0: lst1[0]=lst[x-1] lst1[1]=lst[x] lst1[2]=lst[x+1] if lst1[1]<lst1[0] and lst1[1]<lst1[2]: if lst1[0]>lst1[2]: print(lst1[2]) else: print(lst1[0]) 

This code finds all partial lakes made by filling only the deepest valleys with water, but as shown below, I can have a lake that consists of other lakes.

When entering above 4 3 7 1 3 2 3 5 6 2 1 3 3 2 3 it should print 4 6 3 3 , but my program produces:

4 3 3 2 3

How do I fix my code so that it can find large valleys, such as those that have a small peak in them?

Answer 1

O (n) solution:

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

 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] 

Answer 2

To find the maximum height of the lakes that could potentially form, you need to find all the peaks or points that are higher than the points around them. By changing the code a bit, we can easily get 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, 4 3 7 1 3 2 3 5 6 2 1 3 3 2 3 peaks will be

 [4, 7, 3, 6, 3, 3, 3] 

Now we need to unite the lakes. The way we find which lakes can be combined is to go through the list of peaks, tracking the highest peak so far, and for each peak we delete any previous peaks that are lower than it and the highest peak so far. However, this does not require any additional 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 the lakes, we simply look through the list and display the bottom of each pair. However, there is a wrinkle - with a series of 3, how do we know if it is flat or a lake that separates peaks of equal height? We need to know if the dots are next to each other or not. This can be done by including location information along with each peak -

 peaks.append((lst[x], x)) 

Then, when we go through the final list of peaks, we check the bottom of the two, and if they are equal, we check whether they are next to each other (without them there is no lake).

Just so that I do not write all the code for you, I will leave it to you to change the cycle for working with peaks containing tuples and write a cycle that identifies lakes based on the peaks found.

Regarding time complexity, I believe this is done in linear time. Obviously, we look at the list only once, but in the middle there is a while . At each iteration, the while loop checks at least one peak, but if it ever checks more than one peak, this is because at least one peak has been deleted. Thus, outside the check for one iteration, not a single peak will be checked several times, which gives a no more linear increase in time.

Answer 3

He answered a similar question and, of course, did not think of it. My solution was easy to modify for this version of the question. Key points:

• Find the first peak starting at each end of the list.
• The lower of the two peaks is a strict peak no matter what happens in the middle of the island.
• Start from the bottom peak towards the middle.
• Stop checking when the left peak and right peak meet (wherever it is).

There is a bit of extra accounting reporting to make sure that the final list is in the correct order (from left to right) and that it takes into account peaks that are flat dots (plateau)

Each item in the list is touched only once, therefore it 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 

Answer 4

I also have a solution to the problem, I also added some comments to 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++; } } }