Elevation map solver

elevation-map.js

/*
    You are given an array of non-negative integers that represents a two-dimensional elevation map where each element is unit-width wall and the integer is the height. Suppose it will rain and all spots between two walls get filled up.
    Compute how many units of water remain trapped on the map in O(N) time and O(1) space.
    For example, given the input [2, 1, 2], we can hold 1 unit of water in the middle.
    Given the input [3, 0, 1, 3, 0, 5], we can hold 3 units in the first index, 2 in the second, and 3 in the fourth index (we cannot hold 5 since it would run off to the left), so we can trap 8 units of water.
*/

/**
 * Solution:
 * 
 * Implements simple (and probably not very efficient algorithm as follows):
 * - Create a _matrix_ of zeros and ones where, zeroes represent empty space units and ones are wall units. Width of the matrix is width of the input, height of the matrix is determined by highest element (wall) in the input.
 * - For each row of the matrix, _trim_ leading and ending zeroes, for example, [0, 0, 1, 0, 1, 0] will be trimmed to [1, 0, 1]
 * - For each trimmed row _sum_ the number of empty space units, 
 * - Calculate total sum by reducing total for each row
 */

const matrix = input => {
    const X = input.length;
    const Y = Math.max(...input, 0);
    return Array(Y)
        .fill(0)
        .map((y, i) =>
            Array(X)
                .fill(0)
                .map((x, j) => (input[j] - 1) >= i ? 1 : 0)
        );
};

const trim = row => {    
    const left = row.findIndex(e => e === 1);
    const right = row.lastIndexOf(1);
    return Array(right - left)
        .fill(0)
        .map((e, i) => row[left + i]);
};

const sum = row => {
    return row
        .filter(e => e === 0)
        .reduce((a, b) => a + 1, 0);
};

const reduce = (a, b) => a + b;

const solve = input => {
    return matrix(input)
        .map(trim)
        .map(sum)
        .reduce(reduce, 0);
};

// usage:
// console.log(elevationMap.solve([2, 0, 5, 1, 3, 1, 2]) === 5);