Making A Large Island

Leetcode Problem 827: Making A Large Island

Problem Summary

Given an n x n binary grid where 1 represents land and 0 represents water, you are allowed to change at most one 0 to 1. Return the size of the largest island after applying this operation. An island is a group of 1s connected in four directions (up, down, left, right). The grid dimension n is at most 500.

Techniques

• Array
• Depth-First Search
• Breadth-First Search
• Union-Find
• Matrix

Solution

function dfsArea(row: number, column: number, grid: number[][], label: number): number {
    if (!grid[row] || !grid[row][column] || grid[row][column] != 1) {
        return 0
    }

    grid[row][column] = label
    let area = 1

    area += dfsArea(row, column - 1, grid, label)
    area += dfsArea(row - 1, column, grid, label)
    area += dfsArea(row, column + 1, grid, label)
    area += dfsArea(row + 1, column, grid, label)

    return area
}

function largestIsland(grid: number[][]): number {
    let label = 2
    let areas = new Map<number, number>
    let rows = grid.length
    let columns = grid[0].length

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < columns; j++) {
            if (grid[i][j] === 1) {
                let area = dfsArea(i, j, grid, label)
                areas.set(label, area)
                label++
            }
        }
    }

    let sumOfAreas = 0

    for (const area of areas.values()) {
        sumOfAreas = sumOfAreas + area
    }

    if (rows * columns === sumOfAreas) {
        return sumOfAreas
    }

    let maxArea = 0

    for (let row = 0; row < grid.length; row++) {
        for (let column = 0; column < grid[0].length; column++) {
            if (grid[row][column] === 0) {
                let seen = new Set<number>()
                let leftArea = grid[row] && grid[row][column - 1] ? seen.add(grid[row][column - 1]) ?? 0 : 0
                let topArea = grid[row - 1] && grid[row - 1][column] ? seen.add(grid[row - 1][column]) ?? 0 : 0
                let rightArea = grid[row] && grid[row][column + 1] ? seen.add(grid[row][column + 1]) ?? 0 : 0
                let bottomArea = grid[row + 1] && grid[row + 1][column] ? seen.add(grid[row + 1][column]) ?? 0 : 0
                
                let area = 1
                for (let lbl of seen) {
                    area += areas.get(lbl) ?? 0
                } 

                maxArea = Math.max(maxArea, area)
            }
        }
    }

    return maxArea
};

console.log(largestIsland([[1, 0], [0, 1]])) // 3
console.log(largestIsland([[1, 1], [1, 0]])) // 4
console.log(largestIsland([[1, 1], [1, 1]])) // 4
console.log(largestIsland([[0, 0], [0, 0]])) // 1