findLargestArea.ts

findLargestArea.ts

const grid = [
  [3, 1, 1, 1],
  [2, 1, 0, 1],
  [1, 1, 0, 2],
  [2, 0, 1, 0],
]

interface Area {
    value: number
    points: Set<number>
}

/**
* Find the maximum number of connected values.
* Values are connected vertically and horizontally, but not diagonally.
* @return size of the largest area
*/
function findLargestArea(grid: number[][]): number {
    const minY = 0
    const maxY = grid.length - 1

    if (maxY < 0) { return 0 }

    const minX = 0
    const maxX = grid[maxY].length - 1

    if (maxX < 0) { return 0 }

    const areas = new Map<number, Area>()

    const isOut = (x: number, y: number) => (
        x < minX ||
        x > maxX ||
        y < minY ||
        y > maxY
    )

    // non-negative cantor pairing
    const key = (x: number, y: number) =>
        (.5 * (x + y) * (x + y + 1)) + y

    const value = (x: number, y: number) =>
        isOut(x, y) ? undefined : grid[y][x]

    const area = (x: number, y: number) =>
        areas.get(key(x, y))

    for (let y = minY; y <= maxY; ++y) {
        for (let x = minX; x <= maxX; ++x) {
            const k = key(x, y)
            const v = value(x ,y)!
            const ta = area(x, y - 1)
            const la = area(x - 1, y)

            if (v === ta?.value) {
                ta.points.add(k)
                areas.set(k, ta)
            } else if (v === la?.value) {
                la.points.add(k)
                areas.set(k, la!)
            } else {
                areas.set(k, {
                    value: v,
                    points: new Set([k]),
                })
            }
        }
    }

    return Array.from(new Set(areas.values()))
        .sort((a, b) => b.points.size - a.points.size)[0].points.size
}

console.log(findLargestArea(grid))