TheAlgorithms/Python · error · ValueError

No height can be negative

Error message

No height can be negative

What it means

Raised by trapped_rainwater() when any height in the input iterable is negative. Physical terrain/elevation-bar heights cannot be below zero, and negative values would make the left_max/right_max prefix computations produce meaningless water traps. The check runs after the empty-input early return (which yields 0).

Source

Thrown at dynamic_programming/trapped_water.py:36

    The trapped_rainwater function calculates the total amount of rainwater that can be
    trapped given an array of bar heights.
    It uses a dynamic programming approach, determining the maximum height of bars on
    both sides for each bar, and then computing the trapped water above each bar.
    The function returns the total trapped water.

    >>> trapped_rainwater((0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1))
    6
    >>> trapped_rainwater((7, 1, 5, 3, 6, 4))
    9
    >>> trapped_rainwater((7, 1, 5, 3, 6, -1))
    Traceback (most recent call last):
        ...
    ValueError: No height can be negative
    """
    if not heights:
        return 0
    if any(h < 0 for h in heights):
        raise ValueError("No height can be negative")
    length = len(heights)

    left_max = [0] * length
    left_max[0] = heights[0]
    for i, height in enumerate(heights[1:], start=1):
        left_max[i] = max(height, left_max[i - 1])

    right_max = [0] * length
    right_max[-1] = heights[-1]
    for i in range(length - 2, -1, -1):
        right_max[i] = max(heights[i], right_max[i + 1])

    return sum(
        min(left, right) - height
        for left, right, height in zip(left_max, right_max, heights)
    )

View on GitHub (pinned to f5988cc097)

Solutions

1. Filter or clamp non-physical readings before calling: heights = [max(0, h) for h in heights] if zero-filling is acceptable.
2. Remove sentinel/missing markers (-1, -999) from the series before analysis.
3. Validate upstream: if any(h < 0 for h in heights): fix the data source.

Example fix

# before
trapped_rainwater([7, 1, 5, 3, 6, -1])  # ValueError

# after
heights = [h if h >= 0 else 0 for h in [7, 1, 5, 3, 6, -1]]
trapped_rainwater(heights)

def valid_heights(heights) -> bool:
    return all(h >= 0 for h in heights)

try:
    trapped_rainwater(heights)
except ValueError as e:
    if 'negative' in str(e):
        heights = [max(0, h) for h in heights]
    else:
        raise

When it happens

Trigger: Calling trapped_rainwater((7, 1, 5, 3, 6, -1)) or with any list/tuple containing a negative height, e.g. trapped_rainwater([3, -2, 4]). Empty input does NOT trigger it (returns 0).

Common situations: Sensor data with below-zero noise (e.g. altimeter readings offset by a baseline); sentinel values like -1 used to mark missing readings; coordinate systems where 'down' is negative being passed without normalization.

Related errors

• Limit for the Catalan sequence must be ≥ 0
• Negative arguments are not supported
• iterations must be defined as integers
• starting number must be and integer
• Iterations must be done more than 0 times to play FizzBuzz

AI-assisted analysis of TheAlgorithms/Python@f5988cc097 (2026-08-14). Data as JSON: /api/errors/c21f3f6651cd7b0d. Report an issue: GitHub.