Max Area of Island

Description

doc

Solutions

BFS

const DIRS = [
  [0, 1],
  [-1, 0],
  [0, -1],
  [1, 0],
] // top, right, bottom, left

const search = (grid, i, j) => {
  let queue = [[i, j]]
  let max = 1
  grid[i][j] = 0

  while (queue.length) {
    const [x, y] = queue.shift()

    DIRS.forEach(([_x, _y]) => {
      let newX = x + _x
      let newY = y + _y
      if (grid[newX] && grid[newX][newY]) {
        grid[newX][newY] = 0
        max += 1
        queue.push([newX, newY])
      }
    })
  }

  return max
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function (grid) {
  let max = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j]) {
        max = Math.max(search(grid, i, j), max)
      }
    }
  }

  return max
}

DFS

const DIRS = [
  [0, 1],
  [-1, 0],
  [0, -1],
  [1, 0],
] // top, right, bottom, left

const search = (grid, i, j) => {
  let stack = [[i, j]]
  grid[i][j] = 0

  let count = 1

  while (stack.length) {
    const [x, y] = stack.pop()

    DIRS.forEach(([_x, _y]) => {
      let newX = x + _x
      let newY = y + _y
      if (grid[newX] && grid[newX][newY]) {
        grid[newX][newY] = 0
        count += 1
        stack.push([newX, newY])
      }
    })
  }

  return count
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function (grid) {
  let max = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j]) {
        max = Math.max(search(grid, i, j), max)
      }
    }
  }

  return max
}