Last active
November 8, 2024 18:36
-
-
Save getify/59ab7443723564eb40d20ab7c45d5f0a to your computer and use it in GitHub Desktop.
find size of largest region in matrix... solutions are breadth-first iterative (2) and depth-first recursive (3)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Adapted from: https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/ | |
"use strict"; | |
var M1 = [ | |
[ 0, 0, 1, 1, 0 ], | |
[ 1, 0, 1, 1, 0 ], | |
[ 0, 1, 0, 0, 0 ], | |
[ 0, 0, 0, 1, 1 ] | |
]; | |
console.log( | |
findMaxRegionArea(M1) // 6 | |
); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// iterative breadth-first solution | |
function findMaxRegionArea(matr) { | |
const ROW_LEN = matr[0].length; | |
var area = 0; | |
var maxArea = 0; | |
var visited = new Set(); | |
for (let [ rowIdx, row ] of matr.entries()) { | |
for (let [ colIdx, cell ] of row.entries()) { | |
if ( | |
!visited.has((rowIdx * ROW_LEN) + colIdx) && | |
cell == 1 | |
) { | |
// initialize a breadth-first queue | |
let toVisit = [ [rowIdx, colIdx] ]; | |
while (toVisit.length > 0) { | |
// pull to-visit cell coordinates off the queue | |
let [ visitedRowIdx, visitedColIdx ] = toVisit.shift(); | |
// compute the cell-index | |
let visitedCellIdx = (visitedRowIdx * ROW_LEN) + visitedColIdx; | |
// have we not visited this cell yet? | |
if (!visited.has(visitedCellIdx)) { | |
visited.add(visitedCellIdx); | |
area++; | |
// inspect current row and two (possibly) adjacent rows | |
for (let rowDelta of [ -1, 0, 1 ]) { | |
// inspect current column and two (possibly) adjacent columns | |
for (let colDelta of [ -1, 0, 1 ]) { | |
// avoid re-considering the current cell | |
if (!(rowDelta == 0 && colDelta == 0)) { | |
let toVisitRowIdx = (visitedRowIdx + rowDelta); | |
let toVisitColIdx = (visitedColIdx + colDelta); | |
// is the cell actually in bounds of the matrix, | |
// and is has a `1` in it, and is not already | |
// a cell we've visited/counted? | |
if ( | |
toVisitRowIdx >= 0 && | |
toVisitRowIdx <= (matr.length - 1) && | |
toVisitColIdx >= 0 && | |
toVisitColIdx <= (ROW_LEN - 1) && | |
matr[toVisitRowIdx][toVisitColIdx] == 1 && | |
!visited.has((toVisitRowIdx * ROW_LEN) + toVisitColIdx) | |
) { | |
// schedule visiting this adjacent cell via | |
// the (breadth-first) queue | |
toVisit.push([ toVisitRowIdx, toVisitColIdx ]); | |
} | |
} | |
} | |
} | |
} | |
} | |
// did this region have a bigger area than | |
// we've seen so far? | |
if (area > maxArea) { | |
maxArea = area; | |
} | |
area = 0; | |
} | |
} | |
} | |
return maxArea; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// recursive depth-first solution | |
function findMaxRegionArea(matr) { | |
const ROW_LEN = matr[0].length; | |
var maxArea = 0; | |
var visited = new Set(); | |
for (let [ rowIdx, row ] of matr.entries()) { | |
for (let [ colIdx, cell ] of row.entries()) { | |
if ( | |
!visited.has((rowIdx * ROW_LEN) + colIdx) && | |
cell == 1 | |
) { | |
let area = ( | |
1 + countAdjacentArea( | |
rowIdx, | |
colIdx, | |
visited, | |
ROW_LEN, | |
matr | |
) | |
); | |
// did this region have a bigger area than | |
// we've seen so far? | |
if (area > maxArea) { | |
maxArea = area; | |
} | |
} | |
} | |
} | |
return maxArea; | |
} | |
function countAdjacentArea(visitedRowIdx,visitedColIdx,visited,ROW_LEN,matr) { | |
var area = 0; | |
// compute the cell-index | |
var visitedCellIdx = (visitedRowIdx * ROW_LEN) + visitedColIdx; | |
// have we not visited this cell yet? | |
if (!visited.has(visitedCellIdx)) { | |
visited.add(visitedCellIdx); | |
// inspect current row and two (possibly) adjacent rows | |
for (let rowDelta of [ -1, 0, 1 ]) { | |
// inspect current column and two (possibly) adjacent columns | |
for (let colDelta of [ -1, 0, 1 ]) { | |
// avoid re-considering the current cell | |
if (!(rowDelta == 0 && colDelta == 0)) { | |
let toVisitRowIdx = (visitedRowIdx + rowDelta); | |
let toVisitColIdx = (visitedColIdx + colDelta); | |
// is the cell actually in bounds of the matrix, | |
// and is has a `1` in it, and is not already | |
// a cell we've visited/counted? | |
if ( | |
toVisitRowIdx >= 0 && | |
toVisitRowIdx <= (matr.length - 1) && | |
toVisitColIdx >= 0 && | |
toVisitColIdx <= (ROW_LEN - 1) && | |
matr[toVisitRowIdx][toVisitColIdx] == 1 && | |
!visited.has((toVisitRowIdx * ROW_LEN) + toVisitColIdx) | |
) { | |
// recursively (depth-first) visit all this | |
// cell's unvisited adjacent cells to find | |
// the whole region | |
area += ( | |
1 + countAdjacentArea( | |
toVisitRowIdx, | |
toVisitColIdx, | |
visited, | |
ROW_LEN, | |
matr | |
) | |
); | |
} | |
} | |
} | |
} | |
} | |
return area; | |
} |
Slightly longer solution focusing mostly on readability & straightforwardness:
const shiftSet = (set) => {
const firstValue = set.values().next().value;
set.delete(firstValue);
return firstValue;
}
const getNeighbors = ({
globalIndex,
rowLength,
rowsCount,
}) => {
const rowIndex = Math.floor(globalIndex / rowLength);
const cellIndexInRow = globalIndex % rowLength;
const isCellAtTopBoundary = rowIndex === 0;
const isCellAtLeftBoundary = cellIndexInRow === 0;
const isCellAtRightBoundary = cellIndexInRow + 1 === rowLength;
const isCellAtBottomBoundary = rowIndex + 1 === rowsCount;
const topCellIndex = globalIndex - rowLength;
const topLeftCellIndex = topCellIndex - 1;
const topRightCellIndex = topCellIndex + 1;
const leftCellIndex = globalIndex - 1;
const rightCellIndex = globalIndex + 1;
const bottomCellIndex = globalIndex + rowLength;
const bottomLeftCellIndex = bottomCellIndex - 1;
const bottomRightCellIndex = bottomCellIndex + 1;
const neighbors = [];
if (!isCellAtTopBoundary && !isCellAtLeftBoundary) {
neighbors.push(topLeftCellIndex);
}
if (!isCellAtTopBoundary) {
neighbors.push(topCellIndex);
}
if (!isCellAtTopBoundary && !isCellAtRightBoundary) {
neighbors.push(topRightCellIndex);
}
if (!isCellAtLeftBoundary) {
neighbors.push(leftCellIndex);
}
if (!isCellAtRightBoundary) {
neighbors.push(rightCellIndex);
}
if (!isCellAtBottomBoundary && !isCellAtLeftBoundary) {
neighbors.push(bottomLeftCellIndex);
}
if (!isCellAtBottomBoundary) {
neighbors.push(bottomCellIndex);
}
if (!isCellAtBottomBoundary && !isCellAtRightBoundary) {
neighbors.push(bottomRightCellIndex);
}
return neighbors;
};
const findLargestRegion = (map) => {
let globalIndex = 0;
// Store all filled cells indexes
const filledCellsGlobalIndexes = new Set();
for (let rowIndex = 0; rowIndex < map.length; rowIndex++) {
for (let colIndex = 0; colIndex < map[rowIndex].length; colIndex++, globalIndex++) {
if (!map[rowIndex][colIndex]) {
continue;
}
filledCellsGlobalIndexes.add(globalIndex);
}
}
const rowLength = map[0].length;
const filledAreasSizes = [];
const visitedFilledCellsIndexes = new Map(
Array.from(filledCellsGlobalIndexes).map(index => [index, false])
);
for (const filledCellIndex of filledCellsGlobalIndexes) {
if (visitedFilledCellsIndexes.get(filledCellIndex)) {
continue;
}
let currentFilledAreaCount = 1;
// Mark the starting index as visited
visitedFilledCellsIndexes.set(filledCellIndex, true);
const indexesToVisit = new Set(
getNeighbors({
globalIndex: filledCellIndex,
rowLength,
rowsCount: map.length,
})
);
while (indexesToVisit.size) {
const candidateNeighborIndex = shiftSet(indexesToVisit);
const isNeighborFilled = filledCellsGlobalIndexes.has(candidateNeighborIndex);
const isNeighborVisited = visitedFilledCellsIndexes.get(candidateNeighborIndex);
if (isNeighborFilled && !isNeighborVisited) {
currentFilledAreaCount += 1;
visitedFilledCellsIndexes.set(candidateNeighborIndex, true);
getNeighbors({
globalIndex: candidateNeighborIndex,
rowLength,
rowsCount: map.length,
}).forEach(neighbor => {
if (visitedFilledCellsIndexes.get(neighbor)) {
return;
}
indexesToVisit.add(neighbor);
});
}
}
filledAreasSizes.push(currentFilledAreaCount);
}
const maxArea = Math.max(...filledAreasSizes);
return maxArea > 0 ? maxArea : 0;
};
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
My BFS solution