HR RPT21 V&V - Trapping Rain Water

gistfile1.txt

/**
* OICE
* Input: Array of whole, positive numbers - height of structures 1 wide, array[i] tall to trap water in
* Output: whole, positive number - units of water trapped
* Edge case: [] -> 0, no structures trap water -> 0
* Constraints: 
*/


/**
* Approach 1:
* Constraints: O(n) time, O(n) space
*/

const getWater = (arr) => {
  // Construct an m x n matrix, where m is width of input array, n is maximum num in input arr
  let maxInArr = Math.max.apply(null, arr);
  let matrix = new Array(maxInArr).fill(new Array(arr.length).fill(false));
  
  // ERROR HERE - 
  // Iterate through input arr
  arr.forEach((value, idx) => {
    // For each value, fill the corresponding matrix column with 'true' to indicate a structure
    for (let i = 0; i < value; i++) {
      matrix[maxInArr - 1 - i][idx] = true;
    }
  });
  
  console.log(matrix);
    
  // Set waterTrapped to 0
  // Set maxHeight to 0
  let waterTrapped = 0;
  let maxHeight = 0;

  // For each value in input array (from left -> right)
  for (let i = 0; i < arr.length; i++) {
    // If maxHeight is less than value, set maxHeight to value
    if (maxHeight < arr[i]) maxHeight = arr[i];
    // If maxHeight is greater than value, 
    if (maxHeight > arr[i]) {
      // Insert 'W' (indicating water) into matrix (starting at last row, current col) maxHeight times
      for (let j = 0; j < maxHeight; j++) {
        matrix[maxInArr - 1 - j][i] = 'W';
      }
    }
      
  }

  // Set maxHeight to 0
  maxHeight = 0;

  // For each value in input array (from right -> left)
  for (let i = arr.length - 1; i >= 0; i--) {
    // If maxHeight is less than value, set maxHeight to value
    if (maxHeight < arr[i]) maxHeight = arr[i];
    // If maxHeight is greater than value
    if (maxHeight > arr[i]) {
      // For row = 0 through maxHeight - 1
      for (let j = 0; j < maxHeight; j++) {
        // If matrix square at row, current col is water
        if (matrix[maxInArr - 1 - j][i] === 'W') waterTrapped++;
          // Increment waterTrapped
      }
    }
        
  }

  // Return waterTrapped
  return waterTrapped;
} 

console.log(getWater([0,1,0,2,1,0,1,3,2,1,2,1])); // 6