[RWC] Largest Island 🏝️

largest-island.js

/**
 * @typedef {(0 | 1)[][]} IslandInput
 */

/**
 * @typedef {Object} Island
 * @property {string[]} coordinates
 */

/**
 * Gets a consistent string to refer to a specific coordinate
 * @param {number} row horizontal coordinate of point
 * @param {number} col vertical coordinate of point
 * @returns coordinate's stable string
 */
function getCoordinateKey(row, col) {
	return `row: ${row} | col: ${col}`;
}

/**
 * Finds whether a given coordinate is within the bounds of the grid
 * @param {number} row vertical coordinate of point
 * @param {number} col horizontal coordinate of point
 * @param {IslandInput} grid provided input
 * @returns {boolean} `false` if out of bounds; `true` otherwise
 */
function isPointWithinBounds(row, col, grid) {
	return (
		row >= 0 &&
		row < grid.length &&
		col >= 0 &&
		col < grid[row].length
	);
}

/**
 * Recursively aggregates a list of all points that are contiguously connected to the provided point.
 * @param {number} row vertical coordinate of point
 * @param {number} col horizontal coordinate of point
 * @param {IslandInput} grid provided input
 * @param {Set<string>} foundPoints all contiguous points found so far
 */
function getContiguousPoints(row, col, grid, foundPoints) {
	const currentPointKey = getCoordinateKey(row, col);
	if (foundPoints.has(currentPointKey)) {
		return foundPoints;
	}

	foundPoints.add(currentPointKey);

	const above = {row: row - 1, col};
	const below = {row: row + 1, col};
	const toLeft = {row, col: col - 1};
	const toRight = {row, col: col + 1};

	const unexploredCoordinates = [above, below, toLeft, toRight]
		.filter(candidate => isPointWithinBounds(candidate.row, candidate.col, grid))
		.filter(candidate => grid[candidate.row][candidate.col] === 1)
		.filter(candidate => {
			const candidateKey = getCoordinateKey(candidate.row, candidate.col);
			return !foundPoints.has(candidateKey);
		});

	unexploredCoordinates.forEach(coords => {
		getContiguousPoints(coords.row, coords.col, grid, foundPoints);
	});

	return foundPoints;
}

/**
 * Sorter function for island size, descending order
 * @param {Island} islandA 
 * @param {Island} islandB
 */
function byIslandSize(islandA, islandB) {
	return islandB.coordinates.length - islandA.coordinates.length;
}

/**
 * 
 * @param {IslandInput} input Grid of `0`s and `1`s, where contiguous `1`s are islands
 */
function largestIsland(input) {
	/** @type {Map<string, Island>} */
	const pointIslandAssociations = new Map();

	/** @type {Island[]} */
	const discoveredIslands = [];

	// Discover all islands
	for (let row = 0; row < input.length; row++) {
		for (let col = 0; col < input[row].length; col++) {
			// Not an island
			if (input[row][col] === 0) {
				continue;
			}

			// Already discovered island
			const key = getCoordinateKey(row, col);
			if (pointIslandAssociations.has(key)) {
				continue;
			}

			// Newly discovered island
			const pointsInIsland = getContiguousPoints(row, col, input, new Set());
			/** @type {Island} */
			const island = {
				coordinates: Array.from(pointsInIsland)
			};
			pointsInIsland.forEach(point => {
				pointIslandAssociations.set(point, island);
			});
			discoveredIslands.push(island);
		}
	}

	// Find biggest island
	discoveredIslands.sort(byIslandSize);
	console.log(discoveredIslands[0].coordinates.length, discoveredIslands[0]);
}

const input = [
	[0, 1, 1, 1, 0, 0, 0, 1, 1],
	[0, 1, 1, 1, 0, 1, 0, 0, 0],
	[0, 1, 0, 0, 0, 0, 0, 1, 0],
	[0, 0, 1, 1, 0, 1, 1, 1, 0],
];
largestIsland(input);