Convoy Interview Questions

Given a 2D terrain represented by an array of non-negative integers, where each integer represents the height of a terrain level at that index, implement an algorithm to calculate the total amount of rainwater that can be trapped in this terrain. Consider that rainwater can only be trapped between two terrain levels with higher heights, and the trapped water cannot flow out through the edges.

The algorithm should have an optimal time complexity of O(n) and a space complexity of O(n). Provide a detailed explanation of the algorithm and its implementation in Python.

Example:

In this table, the ‘Index’ row represents the position of the terrain levels, the ‘Terrain Level’ row shows the height of the terrain at each index, and the ‘Trapped Water’ row illustrates the trapped rainwater between the terrain levels. The total trapped rainwater in this example is 7 units (3 + 1 + 3).

Input:

terrainLevels = [3, 0, 2, 0, 4]

Output:

7

In this example, the terrain is represented by the terrainLevels array. The algorithm should calculate the total trapped rainwater, which is 7 units in this case. The trapped rainwater is formed between the heights of 3, 0, 2, 0, and 4.