<jupyter_start><jupyter_text>Water Area[link](https://www.algoexpert.io/questions/Water%20Area)  My Solution<jupyter_code>def waterArea(heights):
    # Write your code here.
    # O(n) time | O(n) space
    leftHeights = [0 for _ in heights]
    maxHeight = 0
    for i in range(1, len(heights)):
        if heights[i - 1] > maxHeight:
            maxHeight = heights[i - 1]
        leftHeights[i] = maxHeight
    
    rightHeights = [0 for _ in heights]
    maxHeight = 0
    for i in reversed(range(len(heights) - 1)):
        if heights[i + 1] > maxHeight:
            maxHeight = heights[i + 1]
        rightHeights[i] = maxHeight
    
    res = [0 for _ in heights]
    for i in range(len(heights)):
        smaller = min(leftHeights[i], rightHeights[i])
        res[i] = smaller - heights[i] if smaller > heights[i] else 0
    return sum(res)
def waterArea(heights):
    # Write your code here.
    # O(n) time | O(1) space
    if heights == []:
        return 0
    tallestIdx = 0
    tallest = heights[0]
    for i in range(len(heights)):
        if heights[i] > tallest:
            tallestIdx = i
            tallest = heights[i]
    res = 0
    leftTallest = 0
    for i in range(1, tallestIdx):
        if heights[i - 1] > leftTallest:
            leftTallest = heights[i - 1]
        res += leftTallest - heights[i] if leftTallest > heights[i] else 0
    rightTallest = 0
    for i in reversed(range(tallestIdx + 1, len(heights) - 1)):
        if heights[i + 1] > rightTallest:
            rightTallest = heights[i + 1]
        res += rightTallest - heights[i] if rightTallest > heights[i] else 0
    
    return res<jupyter_output><empty_output><jupyter_text>Expert Solution<jupyter_code># O(n) time | O(n) space
def waterArea(heights):
    maxes = [0 for x in heights]
    leftMax = 0
    for i in range(len(heights)):
        height = heights[i]
        maxes[i] = leftMax
        leftMax = max(leftMax, height)
    rightMax = 0
    for i in reversed(range(len(heights))):
        height = heights[i]
        minHeight = min(rightMax, maxes[i])
        if height < minHeight:
            maxes[i] = minHeight - height
        else:
            maxes[i] = 0
        rightMax = max(rightMax, height)
    return sum(maxes)
# O(n) time | O(1) space
def waterArea(heights):
    if len(heights) == 0:
        return 0

    leftIdx = 0
    rightIdx = len(heights) - 1
    leftMax = heights[leftIdx]
    rightMax = heights[rightIdx]
    surfaceArea = 0

    while leftIdx < rightIdx:
        if heights[leftIdx] < heights[rightIdx]:
            leftIdx += 1
            leftMax = max(leftMax, heights[leftIdx])
            surfaceArea += leftMax - heights[leftIdx]
        else:
            rightIdx -= 1
            rightMax = max(rightMax - heights[rightIdx])
            surfaceArea += rightMax - heights[rightIdx]

    return surfaceArea<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11114970475859673, 'fraction_numerical': 0.014588398749565822, 'mean_word_length': 2.2542372881355934, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 17, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '87390', 'license': 'MIT', 'n_tokens_mistral': 1028, 'n_tokens_neox': 961, 'n_words': 254, 'path': 'algoExpert/water_area/solution.ipynb', 'repo_name': 'maple1eaf/learning_algorithm', 'size': '2879'}