{"record":{"id":"c21f3f6651cd7b0d","repo":"TheAlgorithms/Python","slug":"no-height-can-be-negative","errorCode":null,"errorMessage":"No height can be negative","messagePattern":"No height can be negative","errorType":"validation","errorClass":"ValueError","httpStatus":null,"severity":"error","filePath":"dynamic_programming/trapped_water.py","lineNumber":36,"sourceCode":"    The trapped_rainwater function calculates the total amount of rainwater that can be\n    trapped given an array of bar heights.\n    It uses a dynamic programming approach, determining the maximum height of bars on\n    both sides for each bar, and then computing the trapped water above each bar.\n    The function returns the total trapped water.\n\n    >>> trapped_rainwater((0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1))\n    6\n    >>> trapped_rainwater((7, 1, 5, 3, 6, 4))\n    9\n    >>> trapped_rainwater((7, 1, 5, 3, 6, -1))\n    Traceback (most recent call last):\n        ...\n    ValueError: No height can be negative\n    \"\"\"\n    if not heights:\n        return 0\n    if any(h < 0 for h in heights):\n        raise ValueError(\"No height can be negative\")\n    length = len(heights)\n\n    left_max = [0] * length\n    left_max[0] = heights[0]\n    for i, height in enumerate(heights[1:], start=1):\n        left_max[i] = max(height, left_max[i - 1])\n\n    right_max = [0] * length\n    right_max[-1] = heights[-1]\n    for i in range(length - 2, -1, -1):\n        right_max[i] = max(heights[i], right_max[i + 1])\n\n    return sum(\n        min(left, right) - height\n        for left, right, height in zip(left_max, right_max, heights)\n    )\n\n","sourceCodeStart":18,"sourceCodeEnd":54,"githubUrl":"https://github.com/TheAlgorithms/Python/blob/f5988cc09713315817df6a7e327e258013a94440/dynamic_programming/trapped_water.py#L18-L54","documentation":"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).","triggerScenarios":"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).","commonSituations":"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.","solutions":["Filter or clamp non-physical readings before calling: heights = [max(0, h) for h in heights] if zero-filling is acceptable.","Remove sentinel/missing markers (-1, -999) from the series before analysis.","Validate upstream: if any(h < 0 for h in heights): fix the data source."],"exampleFix":"# before\ntrapped_rainwater([7, 1, 5, 3, 6, -1])  # ValueError\n\n# after\nheights = [h if h >= 0 else 0 for h in [7, 1, 5, 3, 6, -1]]\ntrapped_rainwater(heights)","handlingStrategy":"validation","validationCode":"def valid_heights(heights) -> bool:\n    return all(h >= 0 for h in heights)","typeGuard":null,"tryCatchPattern":"try:\n    trapped_rainwater(heights)\nexcept ValueError as e:\n    if 'negative' in str(e):\n        heights = [max(0, h) for h in heights]\n    else:\n        raise","preventionTips":["Strip sentinel values (-1, -999) from sensor streams before analysis.","Clamp readings to >= 0 if the baseline is arbitrary.","Unit-test the cleaning step with a fixture containing a negative sample."],"tags":["dynamic-programming","input-validation","data-cleaning"],"backgroundTag":null,"analyzedSha":"f5988cc09713315817df6a7e327e258013a94440","analyzedAt":"2026-08-14T17:30:07.041Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}