00:00:00

Description

Editorial

Terrain Rainwater Retention Analysis

HARD30 pts

A hydrology analytics team stores landscape elevation bars and needs to estimate how much rainwater the profile can hold.

Table: Heights

id: unique position index along the terrain
height: elevation of the bar at that position

Interpretation:

Each bar has width = 1 unit.
Water can accumulate in valleys if taller bars exist on both sides.

Task: Compute the total units of rainwater retained by the full terrain profile.

Per-position principle:

Let left_max be the tallest bar from the start up to the current id.
Let right_max be the tallest bar from the current id to the end.
Water level at the position is min(left_max, right_max).
Trapped water contribution is max(water_level - height, 0).

Output requirements:

Return one row with one column in this exact order: total_trapped_water

Supported submission environments:

SQL (SQLite 3.27.2)
Pandas (Python)

Example

Input

Heights:
| id | height |
|----|--------|
| 1  | 0      |
| 2  | 1      |
| 3  | 0      |
| 4  | 2      |
| 5  | 1      |
| 6  | 0      |
| 7  | 1      |
| 8  | 3      |
| 9  | 2      |
| 10 | 1      |
| 11 | 2      |
| 12 | 1      |

Output

[
  {"total_trapped_water":6}
]

Explanation

Using directional maxima per position, the terrain retains 6 total water units.

Example

Input

Heights:
| id | height |
|----|--------|
| 1  | 4      |
| 2  | 2      |
| 3  | 0      |
| 4  | 3      |
| 5  | 2      |
| 6  | 5      |

Output

[
  {"total_trapped_water":9}
]

Explanation

Multiple valleys are bounded by left and right walls, giving a total of 9.

Example

Input

Heights:
| id | height |
|----|--------|
| 1  | 3      |
| 2  | 3      |
| 3  | 3      |
| 4  | 3      |

Output

[
  {"total_trapped_water":0}
]

Explanation

Flat terrain has no lower basin between taller boundaries, so no water is retained.

Accepted0/0·0% Acceptance

Constraints

1 <= number of rows in Heights <= 200000
1 <= id <= 1000000000
id values are unique and sequential within each test case
0 <= height <= 100000
height is an integer
Each bar has unit width
Return exactly one row
Output column must be exactly: total_trapped_water
Use SQLite 3.27.2 semantics for SQL submissions
For Pandas submissions, return a DataFrame with column [total_trapped_water]

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

Heights =

[{"id":1,"height":0},{"id":2,"height":1},{"id":3,"height":0},{"id":4,"height":2},{"id":5,"height":1},{"id":6,"height":0},{"id":7,"height":1},{"id":8,"height":3},{"id":9,"height":2},{"id":10,"height":1},{"id":11,"height":2},{"id":12,"height":1}]

Loading problem...

101

00:00:00

Description

Editorial

Terrain Rainwater Retention Analysis

HARD30 pts

A hydrology analytics team stores landscape elevation bars and needs to estimate how much rainwater the profile can hold.

Table: Heights

id: unique position index along the terrain
height: elevation of the bar at that position

Interpretation:

Each bar has width = 1 unit.
Water can accumulate in valleys if taller bars exist on both sides.

Task: Compute the total units of rainwater retained by the full terrain profile.

Per-position principle:

Let left_max be the tallest bar from the start up to the current id.
Let right_max be the tallest bar from the current id to the end.
Water level at the position is min(left_max, right_max).
Trapped water contribution is max(water_level - height, 0).

Output requirements:

Return one row with one column in this exact order: total_trapped_water

Supported submission environments:

SQL (SQLite 3.27.2)
Pandas (Python)

Example

Input

Heights:
| id | height |
|----|--------|
| 1  | 0      |
| 2  | 1      |
| 3  | 0      |
| 4  | 2      |
| 5  | 1      |
| 6  | 0      |
| 7  | 1      |
| 8  | 3      |
| 9  | 2      |
| 10 | 1      |
| 11 | 2      |
| 12 | 1      |

Output

[
  {"total_trapped_water":6}
]

Explanation

Using directional maxima per position, the terrain retains 6 total water units.

Example

Input

Heights:
| id | height |
|----|--------|
| 1  | 4      |
| 2  | 2      |
| 3  | 0      |
| 4  | 3      |
| 5  | 2      |
| 6  | 5      |

Output

[
  {"total_trapped_water":9}
]

Explanation

Multiple valleys are bounded by left and right walls, giving a total of 9.

Example

Input

Heights:
| id | height |
|----|--------|
| 1  | 3      |
| 2  | 3      |
| 3  | 3      |
| 4  | 3      |

Output

[
  {"total_trapped_water":0}
]

Explanation

Flat terrain has no lower basin between taller boundaries, so no water is retained.

Accepted0/0·0% Acceptance

Constraints

1 <= number of rows in Heights <= 200000
1 <= id <= 1000000000
id values are unique and sequential within each test case
0 <= height <= 100000
height is an integer
Each bar has unit width
Return exactly one row
Output column must be exactly: total_trapped_water
Use SQLite 3.27.2 semantics for SQL submissions
For Pandas submissions, return a DataFrame with column [total_trapped_water]

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

Heights =

Terrain Rainwater Retention Analysis

Hints

Terrain Rainwater Retention Analysis

Hints