202408192028
tags: #dfs

var largestIsland = function(grid) {
	const n = grid.length;
	const DIRS = [[0, 1], [1, 0], [-1, 0], [0, -1]];
	let index = 3, res = 0;
	const areaMap = new Map();
	
	const dfs = (i, j, index) => {
		if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] !== 1) {
			return 0;
		}
		grid[i][j] = index;
		let totalArea = 1;
		for (const [dx, dy] of DIRS) {
			totalArea += dfs(i + dx, j + dy, index);
		}
		return totalArea;
	};
	
	const nearbyConnectedArea = (i, j) => {
		let totalArea = 1;
		const areaIndexSet = new Set();
		for (const [dx, dy] of DIRS) {
			const x = i + dx;
			const y = j + dy;
			if (x < 0 || x >= n || y < 0 || y >= n) {
				continue;
			}
			const areaIndex = grid[x][y];
			if (areaMap.has(areaIndex) && !areaIndexSet.has(areaIndex)) {
			areaIndexSet.add(areaIndex);
				totalArea += areaMap.get(areaIndex);
			}
		}
		return totalArea;
	}
	
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j] === 1) {
				areaMap.set(index, dfs(i, j, index));
				res = Math.max(res, areaMap.get(index));
				index += 1;
			}
		}
	}
	
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j] === 0) {
				res = Math.max(res, nearbyConnectedArea(i, j));
			}
		}
	} 

	return res;
};

Reference

https://leetcode.com/problems/making-a-large-island