interface Cells {
    i: number;
    j: number;
    visited: boolean;
    height: number;
}

interface IHeap {
    i: number;
    j: number;
    height: number;
}

class MinHeap {

    private items: IHeap[] = [];

    get length(): number {
        return this.items.length;
    }

    push(item: IHeap): void {

        this.items.push(item);
        this.items.sort((a, b) => a.height - b.height);

    }

    pop(): IHeap | undefined {

        return this.items.shift();

    }

}

const mapToObjectArray = (heights: number[][]): Cells[][] => {

    const array: Cells[][] = [];

    for (let i = 0; i < heights.length; i++) {

        const subArray: Cells[] = [];

        for (let j = 0; j < heights[i].length; j++) {

            subArray.push({ i, j, visited: false, height: heights[i][j] });

        }

        array.push(subArray);

    }

    return array;

}

const initHeap = (heights: number[][]): MinHeap => {

    const heap = new MinHeap();

    for (let i = 0; i < heights.length; i++) {

        for (let j = 0; j < heights[i].length; j++) {

            if (i === 0 || j === 0 || i === heights.length - 1 || j === heights[i].length - 1) {
                heap.push({ i, j, height: heights[i][j] });
            }

        }

    }

    return heap;

}

const markBordersVisited = (cells: Cells[][], heights: number[][]) => {

    for (let i = 0; i < heights.length; i++) {

        for (let j = 0; j < heights[i].length; j++) {

            if (i === 0 || j === 0 || i === heights.length - 1 || j === heights[i].length - 1) {
                cells[i][j].visited = true;
            }

        }

    }

}

const extractNeighbors = (cells: Cells[][], itemHeap: IHeap): Cells[] => {

    const { i, j } = itemHeap;

    const neighborTop = cells?.[i - 1]?.[j];
    const neighborRight = cells?.[i]?.[j + 1];
    const neighborBottom = cells?.[i + 1]?.[j];
    const neighborLeft = cells?.[i]?.[j - 1];

    return [
        neighborTop,
        neighborRight,
        neighborBottom,
        neighborLeft
    ].filter((n) => !!n && !n.visited);

}

const evaluate = (cells: Cells[][], heap: MinHeap) => {

    let water = 0;

    while (heap.length) {

        const currentHeap = heap.pop()!;

        const validNeighbors = extractNeighbors(cells, currentHeap);

        for (const neighbor of validNeighbors) {

            const neighborLevel = Math.max(neighbor.height, currentHeap.height);
            const detainedWater = neighborLevel - neighbor.height;

            water = water + detainedWater;

            neighbor.visited = true;

            heap.push({
                i: neighbor.i,
                j: neighbor.j,
                height: neighborLevel
            });

        }

    }

    return water;

}

export function trapRainWater2D(heights: number[][]): number {

    const x = heights.length;
    const y = heights?.[0].length;

    if (x < 3 || y < 3) {
        return 0;
    }

    if (x > 200 || y > 200) {
        return 0;
    }

    const cells = mapToObjectArray(heights);

    const heap = initHeap(heights);

    markBordersVisited(cells, heights);

    return evaluate(cells, heap);

}