function isValid(i, j, r, c) {
  if (0 <= i && i < r && 0 <= j && j < c) return true;
  return false;
}

const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

function getNeighbors(i, j, r, c) {
  let neighbors = [];
  for (let p = 0; p < 4; p++) {
    if (isValid(i + dr[p], j + dc[p], r, c)) {
      neighbors.push([i + dr[p], j + dc[p]]);
    }
  }
  return neighbors;
}

function travel(grid, i, j, type, result, visited, continentId, lakeId) {
  let r = grid.length;
  let c = grid[0].length;

  if (visited[i][j]) {
    return;
  }
  visited[i][j] = true;
  result[i][j].type = type;
  result[i][j].continentId = continentId;
  result[i][j].lakeId = lakeId;
  const neighbors = getNeighbors(i, j, r, c);

  for (const neighbor of neighbors) {
    if (grid[i][j] == grid[neighbor[0]][neighbor[1]]) {
      travel(
        grid,
        neighbor[0],
        neighbor[1],
        type,
        result,
        visited,
        continentId,
        lakeId
      );
    }
  }
}

function solveGrid(grid) {
  let r = grid.length;
  let c = grid[0].length;

  let solution = new Array(r);
  let visited = new Array(r);

  for (let i = 0; i < r; i++) {
    solution[i] = new Array(c);
    visited[i] = new Array(c);

    for (let j = 0; j < c; j++) {
      const item = {
        type: "",
      };
      solution[i][j] = item;
      visited[i][j] = false;
    }
  }

  let area = 0;
  for (let j = 0; j < c; j++) {
    if (grid[0][j] == 0) {
      travel(
        grid,
        0,
        j,
        "ocean",
        solution,
        visited,
        undefined,
        undefined,
        area
      );
    }
    if (grid[r - 1][j] == 0) {
      travel(
        grid,
        r - 1,
        j,
        "ocean",
        solution,
        visited,
        undefined,
        undefined,
        area
      );
    }
  }

  for (let i = 0; i < r; i++) {
    if (grid[i][0] == 0) {
      travel(grid, i, 0, "ocean", solution, visited);
    }
    if (grid[i][c - 1] == 0) {
      travel(grid, i, c - 1, "ocean", solution, visited);
    }
  }

  let continentNumber = 0;
  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      if (grid[i][j] == 1 && visited[i][j] == false) {
        continentNumber++;
        travel(grid, i, j, "land", solution, visited, continentNumber);
      }
    }
  }

  console.log("Continents Found", continentNumber);

  let lakeNumber = 0;
  for (let i = 1; i < r - 1; i++) {
    for (let j = 1; j < c - 1; j++) {
      if (visited[i][j] == false) {
        lakeNumber++;
        travel(grid, i, j, "lake", solution, visited, undefined, lakeNumber);
      }
    }
  }
  console.log("Lakes Found", lakeNumber);

  let lakeContinentMap = {};

  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      if (solution[i][j].type == "lake") {
        const neighbors = getNeighbors(i, j, r, c);
        for (const neighbor of neighbors) {
          if (solution[neighbor[0]][neighbor[1]].type == "land") {
            console.log(
              "Found boundary continent",
              solution[i][j].lakeId,
              solution[neighbor[0]][neighbor[1]].continentId
            );
            lakeContinentMap[solution[i][j].lakeId] =
              solution[neighbor[0]][neighbor[1]].continentId;
          }
        }
      }
    }
  }

  let continentAreaMap = {};
  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      if (solution[i][j].type == "land") {
        const continent = solution[i][j].continentId;
        if (continentAreaMap[continent] == undefined) {
          continentAreaMap[continent] = 1;
        } else {
          continentAreaMap[continent]++;
        }
      }
    }
  }

  let lakeAreaMap = {};
  for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
      if (solution[i][j].type == "lake") {
        const lakeId = solution[i][j].lakeId;
        if (lakeAreaMap[lakeId] == undefined) {
          lakeAreaMap[lakeId] = 1;
        } else {
          lakeAreaMap[lakeId]++;
        }
      }
    }
  }

  let maxLakeArea = 0;
  let maxAreaContinentId = null;
  let continentTotalLakeAreaMap = {};

  Object.entries(lakeAreaMap).forEach(([lakeId, lakeArea]) => {
    if (lakeArea > maxLakeArea) {
      maxLakeArea = lakeArea;
      maxAreaContinentId = lakeContinentMap[lakeId];
    }
  });

  for (let i = 1; i <= continentNumber; i++) {
    // get all lakes for the continent
    let totalLakeArea = 0;
    Object.entries(lakeContinentMap).forEach(([lakeId, continentId]) => {
      if (continentId == i) {
        totalLakeArea += lakeAreaMap[lakeId];
      }
    });

    continentTotalLakeAreaMap[i] = totalLakeArea;
  }

  return {
    solution,
    lakeContinentMap,
    lakeAreaMap,
    continentTotalLakeAreaMap,
    maxLakeArea,
    continentAreaMap,
    maxAreaContinentId,
    totalArea:
      continentTotalLakeAreaMap[maxAreaContinentId] +
      continentAreaMap[maxAreaContinentId],
  };
}