Rain Terraces

Definition

Definition

The Rain Terraces Algorithm is a technique used to calculate the total volume of water that can be trapped between terraces formed by an elevation map

Explanation

Iterate through the elevation map and calculating the amount of water that can be trapped between the terraces formed by the varying heights. It uses two pointers approach to keep track of the maximum height seen so far from the left and right side for each element. The trapped water for each element is then calculated based on the difference between the minimum of the maximum heights on both sides and the height of the current element

Guidance

• Initialize variables: left_max, right_max, and water_volume to 0
• Iterate through each element in the elevation map
  • for each element, update left_max = max(left_max, elevation_map[i])
  • iterate from the end of the elevation map to the current element and update right_max similarly
  • calculate the trapped water for the current element: trapped_water = min(left_max, right_max) - elevation_map[i]
  • add the calculated trapped water to the total water volume
  • repeat steps until all elements in the elevation map are processed
• Return the total water volume as the result

Tips

• keep track of the maximum height seen from both sides for each element efficiently to optimize the algorithm's performance
• handle edge cases such as empty elevation maps or maps with fewer than three elements appropriately

Practice

Practice

rainTerraces(elevation_map):
  left_max = 0
  right_max = 0
  water_volume = 0

  for i from 0 to length(elevation_map) - 1:
    left_max = max(left_max, elevation_map[i])

  for i from length(elevation_map) - 1 to 0:
    right_max = max(right_max, elevation_map[i])

  for i from 0 to length(elevation_map) - 1:
    water_volume += min(left_max, right_max) - elevation_map[i]
    left_max = max(left_max, elevation_map[i])

  return water_volume

Solution

package main

func bruteforceRainTerraces(terraces []int) int {
	waterAmount := 0

	for terraceIndex := 0; terraceIndex < len(terraces); terraceIndex++ {
		leftHighestLevel := 0
		for leftIndex := terraceIndex - 1; leftIndex >= 0; leftIndex-- {
			leftHighestLevel = max(leftHighestLevel, terraces[leftIndex])
		}

		rightHighestLevel := 0
		for rightIndex := terraceIndex + 1; rightIndex < len(terraces); rightIndex++ {
			rightHighestLevel = max(rightHighestLevel, terraces[rightIndex])
		}

		terraceBoundaryLevel := min(leftHighestLevel, rightHighestLevel)
		if terraceBoundaryLevel > terraces[terraceIndex] {
			waterAmount += terraceBoundaryLevel - terraces[terraceIndex]
		}
	}

	return waterAmount
}

func dynamicProgrammingRainTerraces(terraces []int) int {
	waterAmount := 0

	leftMaxLevels := make([]int, len(terraces))
	rightMaxLevels := make([]int, len(terraces))

	leftMaxLevels[0] = terraces[0]
	for terraceIndex := 1; terraceIndex < len(terraces); terraceIndex++ {
		leftMaxLevels[terraceIndex] = max(terraces[terraceIndex], leftMaxLevels[terraceIndex-1])
	}

	rightMaxLevels[len(terraces)-1] = terraces[len(terraces)-1]
	for terraceIndex := len(terraces) - 2; terraceIndex >= 0; terraceIndex-- {
		rightMaxLevels[terraceIndex] = max(terraces[terraceIndex], rightMaxLevels[terraceIndex+1])
	}

	for terraceIndex := 0; terraceIndex < len(terraces); terraceIndex++ {
		currentTerraceBoundary := min(leftMaxLevels[terraceIndex], rightMaxLevels[terraceIndex])

		if currentTerraceBoundary > terraces[terraceIndex] {
			waterAmount += currentTerraceBoundary - terraces[terraceIndex]
		}
	}

	return waterAmount
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

public class RainTerraces {

  public static int bruteforceRainTerraces(int[] terraces) {
    int waterAmount = 0;

    for (int terraceIndex = 0; terraceIndex < terraces.length; terraceIndex++) {
      int leftHighestLevel = 0;
      for (int leftIndex = terraceIndex - 1; leftIndex >= 0; leftIndex--) {
        leftHighestLevel = Math.max(leftHighestLevel, terraces[leftIndex]);
      }

      int rightHighestLevel = 0;
      for (int rightIndex = terraceIndex + 1; rightIndex < terraces.length; rightIndex++) {
        rightHighestLevel = Math.max(rightHighestLevel, terraces[rightIndex]);
      }

      int terraceBoundaryLevel = Math.min(leftHighestLevel, rightHighestLevel);
      if (terraceBoundaryLevel > terraces[terraceIndex]) {
        waterAmount += terraceBoundaryLevel - terraces[terraceIndex];
      }
    }

    return waterAmount;
  }

  public static int dynamicProgrammingRainTerraces(int[] terraces) {
    int waterAmount = 0;

    int[] leftMaxLevels = new int[terraces.length];
    int[] rightMaxLevels = new int[terraces.length];

    leftMaxLevels[0] = terraces[0];
    for (int terraceIndex = 1; terraceIndex < terraces.length; terraceIndex++) {
      leftMaxLevels[terraceIndex] = Math.max(terraces[terraceIndex], leftMaxLevels[terraceIndex - 1]);
    }

    rightMaxLevels[terraces.length - 1] = terraces[terraces.length - 1];
    for (int terraceIndex = terraces.length - 2; terraceIndex >= 0; terraceIndex--) {
      rightMaxLevels[terraceIndex] = Math.max(terraces[terraceIndex], rightMaxLevels[terraceIndex + 1]);
    }

    for (int terraceIndex = 0; terraceIndex < terraces.length; terraceIndex++) {
      int currentTerraceBoundary = Math.min(leftMaxLevels[terraceIndex], rightMaxLevels[terraceIndex]);

      if (currentTerraceBoundary > terraces[terraceIndex]) {
        waterAmount += currentTerraceBoundary - terraces[terraceIndex];
      }
    }

    return waterAmount;
  }
}

function bruteforceRainTerraces(terraces) {
  let waterAmount = 0;

  for (
    let terraceIndex = 0;
    terraceIndex < terraces.length;
    terraceIndex += 1
  ) {
    let leftHighestLevel = 0;
    for (let leftIndex = terraceIndex - 1; leftIndex >= 0; leftIndex -= 1) {
      leftHighestLevel = Math.max(leftHighestLevel, terraces[leftIndex]);
    }

    let rightHighestLevel = 0;
    for (
      let rightIndex = terraceIndex + 1;
      rightIndex < terraces.length;
      rightIndex += 1
    ) {
      rightHighestLevel = Math.max(rightHighestLevel, terraces[rightIndex]);
    }

    const terraceBoundaryLevel = Math.min(leftHighestLevel, rightHighestLevel);
    if (terraceBoundaryLevel > terraces[terraceIndex]) {
      waterAmount += terraceBoundaryLevel - terraces[terraceIndex];
    }
  }

  return waterAmount;
}

function dynamicProgrammingRainTerraces(terraces) {
  let waterAmount = 0;

  const leftMaxLevels = new Array(terraces.length).fill(0);
  const rightMaxLevels = new Array(terraces.length).fill(0);

  [leftMaxLevels[0]] = terraces;
  for (
    let terraceIndex = 1;
    terraceIndex < terraces.length;
    terraceIndex += 1
  ) {
    leftMaxLevels[terraceIndex] = Math.max(
      terraces[terraceIndex],
      leftMaxLevels[terraceIndex - 1],
    );
  }

  rightMaxLevels[terraces.length - 1] = terraces[terraces.length - 1];
  for (
    let terraceIndex = terraces.length - 2;
    terraceIndex >= 0;
    terraceIndex -= 1
  ) {
    rightMaxLevels[terraceIndex] = Math.max(
      terraces[terraceIndex],
      rightMaxLevels[terraceIndex + 1],
    );
  }

  for (
    let terraceIndex = 0;
    terraceIndex < terraces.length;
    terraceIndex += 1
  ) {
    const currentTerraceBoundary = Math.min(
      leftMaxLevels[terraceIndex],
      rightMaxLevels[terraceIndex],
    );

    if (currentTerraceBoundary > terraces[terraceIndex]) {
      waterAmount += currentTerraceBoundary - terraces[terraceIndex];
    }
  }

  return waterAmount;
}

fun bruteforceRainTerraces(terraces: IntArray): Int {
    var waterAmount = 0

    for (terraceIndex in terraces.indices) {
        var leftHighestLevel = 0
        for (leftIndex in terraceIndex - 1 downTo 0) {
            leftHighestLevel = maxOf(leftHighestLevel, terraces[leftIndex])
        }

        var rightHighestLevel = 0
        for (rightIndex in terraceIndex + 1 until terraces.size) {
            rightHighestLevel = maxOf(rightHighestLevel, terraces[rightIndex])
        }

        val terraceBoundaryLevel = minOf(leftHighestLevel, rightHighestLevel)
        if (terraceBoundaryLevel > terraces[terraceIndex]) {
            waterAmount += terraceBoundaryLevel - terraces[terraceIndex]
        }
    }

    return waterAmount
}

fun dynamicProgrammingRainTerraces(terraces: IntArray): Int {
    var waterAmount = 0

    val leftMaxLevels = IntArray(terraces.size) { 0 }
    val rightMaxLevels = IntArray(terraces.size) { 0 }

    leftMaxLevels[0] = terraces[0]
    for (terraceIndex in 1 until terraces.size) {
        leftMaxLevels[terraceIndex] = maxOf(terraces[terraceIndex], leftMaxLevels[terraceIndex - 1])
    }

    rightMaxLevels[terraces.size - 1] = terraces[terraces.size - 1]
    for (terraceIndex in terraces.size - 2 downTo 0) {
        rightMaxLevels[terraceIndex] = maxOf(terraces[terraceIndex], rightMaxLevels[terraceIndex + 1])
    }

    for (terraceIndex in terraces.indices) {
        val currentTerraceBoundary = minOf(leftMaxLevels[terraceIndex], rightMaxLevels[terraceIndex])

        if (currentTerraceBoundary > terraces[terraceIndex]) {
            waterAmount += currentTerraceBoundary - terraces[terraceIndex]
        }
    }

    return waterAmount
}

def bruteforceRainTerraces(terraces):
    waterAmount = 0

    for terraceIndex in range(len(terraces)):
        leftHighestLevel = 0
        for leftIndex in range(terraceIndex - 1, -1, -1):
            leftHighestLevel = max(leftHighestLevel, terraces[leftIndex])

        rightHighestLevel = 0
        for rightIndex in range(terraceIndex + 1, len(terraces)):
            rightHighestLevel = max(rightHighestLevel, terraces[rightIndex])

        terraceBoundaryLevel = min(leftHighestLevel, rightHighestLevel)
        if terraceBoundaryLevel > terraces[terraceIndex]:
            waterAmount += terraceBoundaryLevel - terraces[terraceIndex]

    return waterAmount


def dynamicProgrammingRainTerraces(terraces):
    waterAmount = 0

    leftMaxLevels = [0] * len(terraces)
    rightMaxLevels = [0] * len(terraces)

    leftMaxLevels[0] = terraces[0]
    for terraceIndex in range(1, len(terraces)):
        leftMaxLevels[terraceIndex] = max(terraces[terraceIndex], leftMaxLevels[terraceIndex - 1])

    rightMaxLevels[len(terraces) - 1] = terraces[len(terraces) - 1]
    for terraceIndex in range(len(terraces) - 2, -1, -1):
        rightMaxLevels[terraceIndex] = max(terraces[terraceIndex], rightMaxLevels[terraceIndex + 1])

    for terraceIndex in range(len(terraces)):
        currentTerraceBoundary = min(leftMaxLevels[terraceIndex], rightMaxLevels[terraceIndex])

        if currentTerraceBoundary > terraces[terraceIndex]:
            waterAmount += currentTerraceBoundary - terraces[terraceIndex]

    return waterAmount

fn bruteforce_rain_terraces(terraces: &[i32]) -> i32 {
    let mut water_amount = 0;

    for terrace_index in 0..terraces.len() {
        let mut left_highest_level = 0;
        for left_index in (0..terrace_index).rev() {
            left_highest_level = left_highest_level.max(terraces[left_index]);
        }

        let mut right_highest_level = 0;
        for right_index in (terrace_index + 1)..terraces.len() {
            right_highest_level = right_highest_level.max(terraces[right_index]);
        }

        let terrace_boundary_level = left_highest_level.min(right_highest_level);
        if terrace_boundary_level > terraces[terrace_index] {
            water_amount += terrace_boundary_level - terraces[terrace_index];
        }
    }

    water_amount
}

fn dynamic_programming_rain_terraces(terraces: &[i32]) -> i32 {
    let mut water_amount = 0;

    let mut left_max_levels = vec![0; terraces.len()];
    let mut right_max_levels = vec![0; terraces.len()];

    left_max_levels[0] = terraces[0];
    for terrace_index in 1..terraces.len() {
        left_max_levels[terrace_index] =
            terraces[terrace_index].max(left_max_levels[terrace_index - 1]);
    }

    right_max_levels[terraces.len() - 1] = terraces[terraces.len() - 1];
    for terrace_index in (0..terraces.len() - 1).rev() {
        right_max_levels[terrace_index] =
            terraces[terrace_index].max(right_max_levels[terrace_index + 1]);
    }

    for terrace_index in 0..terraces.len() {
        let current_terrace_boundary = left_max_levels[terrace_index]
            .min(right_max_levels[terrace_index]);

        if current_terrace_boundary > terraces[terrace_index] {
            water_amount += current_terrace_boundary - terraces[terrace_index];
        }
    }

    water_amount
}

function bruteforceRainTerraces(terraces: number[]): number {
  let waterAmount = 0;

  for (
    let terraceIndex = 0;
    terraceIndex < terraces.length;
    terraceIndex += 1
  ) {
    let leftHighestLevel = 0;
    for (let leftIndex = terraceIndex - 1; leftIndex >= 0; leftIndex -= 1) {
      leftHighestLevel = Math.max(leftHighestLevel, terraces[leftIndex]);
    }

    let rightHighestLevel = 0;
    for (
      let rightIndex = terraceIndex + 1;
      rightIndex < terraces.length;
      rightIndex += 1
    ) {
      rightHighestLevel = Math.max(rightHighestLevel, terraces[rightIndex]);
    }

    const terraceBoundaryLevel = Math.min(leftHighestLevel, rightHighestLevel);
    if (terraceBoundaryLevel > terraces[terraceIndex]) {
      waterAmount += terraceBoundaryLevel - terraces[terraceIndex];
    }
  }

  return waterAmount;
}

function dynamicProgrammingRainTerraces(terraces: number[]): number {
  let waterAmount = 0;

  const leftMaxLevels: number[] = new Array(terraces.length).fill(0);
  const rightMaxLevels: number[] = new Array(terraces.length).fill(0);

  [leftMaxLevels[0]] = terraces;
  for (
    let terraceIndex = 1;
    terraceIndex < terraces.length;
    terraceIndex += 1
  ) {
    leftMaxLevels[terraceIndex] = Math.max(
      terraces[terraceIndex],
      leftMaxLevels[terraceIndex - 1],
    );
  }

  rightMaxLevels[terraces.length - 1] = terraces[terraces.length - 1];
  for (
    let terraceIndex = terraces.length - 2;
    terraceIndex >= 0;
    terraceIndex -= 1
  ) {
    rightMaxLevels[terraceIndex] = Math.max(
      terraces[terraceIndex],
      rightMaxLevels[terraceIndex + 1],
    );
  }

  for (
    let terraceIndex = 0;
    terraceIndex < terraces.length;
    terraceIndex += 1
  ) {
    const currentTerraceBoundary = Math.min(
      leftMaxLevels[terraceIndex],
      rightMaxLevels[terraceIndex],
    );

    if (currentTerraceBoundary > terraces[terraceIndex]) {
      waterAmount += currentTerraceBoundary - terraces[terraceIndex];
    }
  }

  return waterAmount;
}