islands.js

const map = [
  [1, 0, 1, 0, 0, 0, 1, 1, 1, 1],
  [0, 0, 1, 0, 1, 0, 1, 0, 0, 0],
  [1, 1, 1, 1, 0, 0, 1, 0, 0, 0],
  [1, 0, 0, 1, 0, 1, 0, 0, 0, 0],
  [1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
  [0, 1, 0, 1, 0, 0, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
  [0, 0, 0, 1, 0, 0, 1, 1, 1, 0],
  [1, 0, 1, 0, 1, 0, 0, 1, 0, 0],
  [1, 1, 1, 1, 0, 0, 0, 1, 1, 1],
]

// const map = [
//   [1, 0, 1, 0],
//   [0, 0, 1, 0],
//   [0, 0, 1, 1],
//   [0, 0, 0, 0],
// ]

class Queue {
  constructor() {
    this.data = []
  }

  enqueue(element) {
    this.data.push(element)
  }

  dequeue() {
    return this.data.shift()
  }
}

function countIslands(map) {
  const islands = []
  const visited = new Set()

  const height = map.length
  const width = map[0].length

  function isUnseen(x, y) {
    return !visited.has([x, y].toString())
  }

  function visit(x, y) {
    visited.add([x, y].toString())
  }

  function bfsCount(x, y) {
    let count = 1
    visit(x, y)
    const queue = new Queue()
    let current = [x, y]
    while (current) {
      const cx = current[0]
      const cy = current[1]
      for (let dx = -1; dx <= 1; dx++) {
        for (let dy = -1; dy <= 1; dy++) {
          const nx = cx + dx
          const ny = cy + dy

          if (
            !(dx === 0 && dy === 0) &&
            nx >= 0 &&
            nx < width &&
            ny >= 0 &&
            ny < height
          ) {
            if (isUnseen(nx, ny) && map[ny][nx] > 0) {
              visit(nx, ny)
              queue.enqueue([nx, ny])
              count++
            }
          }
        }
      }
      current = queue.dequeue()
    }
    return count
  }

  for (let y = 0; y < map.length; y++) {
    for (let x = 0; x < map[y].length; x++) {
      if (map[y][x] > 0 && isUnseen(x, y)) {
        const size = bfsCount(x, y)
        islands.push(size)
      }
    }
  }

  return islands.sort((a, b) => a - b)
}

console.log(countIslands(map))
console.log('----')