var numIslands = function (grid) {

    let numberOfIslands = 0;
    let currentMode = "find_land";
    let numberOfSubArrays = grid.length;
    let eachSubArraySize = grid[0]?.length;
    let dfsStack = [];
    let blocksAddedToTheFrontier = {}
    let continueMainLoop = true;

    let currentExplorationIndex = {
        subArrayIndex: 0,
        subArrayElementIndex: 0
    }

    if (numberOfSubArrays == 0 || eachSubArraySize == 0) {
        return 0;
    }

    const moveToNextLocation = () => {
        let newSubArrayIndex = currentExplorationIndex.subArrayIndex;
        let newSubArrayElementIndex = currentExplorationIndex.subArrayElementIndex + 1;

        if (newSubArrayElementIndex == eachSubArraySize) {
            newSubArrayElementIndex = 0;
            newSubArrayIndex = newSubArrayIndex + 1;
        }

        if (newSubArrayIndex == numberOfSubArrays) {
            currentExplorationIndex = {
                subArrayIndex: undefined,
                subArrayElementIndex: undefined
            }
            continueMainLoop = false;
            return;
        }

        currentExplorationIndex = {
            subArrayIndex: newSubArrayIndex,
            subArrayElementIndex: newSubArrayElementIndex
        }
    }

    const addLocationToQueue = (locationObj) => {
        let hashKey = `${locationObj.subArrayIndex}-${locationObj.subArrayElementIndex}`;
        if (blocksAddedToTheFrontier[hashKey] == true) {
            return;
        } else {
            blocksAddedToTheFrontier[hashKey] = true;
            dfsStack.push({ ...locationObj })
        }
    }

    const expandFrontier = (startingBlock) => {
        let blockAbove = {
            subArrayIndex: startingBlock.subArrayIndex - 1,
            subArrayElementIndex: startingBlock.subArrayElementIndex
        }

        let blockBelow = {
            subArrayIndex: startingBlock.subArrayIndex + 1,
            subArrayElementIndex: startingBlock.subArrayElementIndex
        }

        let blockOnRight = {
            subArrayIndex: startingBlock.subArrayIndex,
            subArrayElementIndex: startingBlock.subArrayElementIndex + 1
        }

        let blockOnLeft = {
            subArrayIndex: startingBlock.subArrayIndex,
            subArrayElementIndex: startingBlock.subArrayElementIndex - 1
        }

        let allPossibleBlockToAddToFrontier = [
            blockAbove, blockBelow, blockOnRight, blockOnLeft
        ]

        let onlyBlocksThatHaveLand = allPossibleBlockToAddToFrontier.filter((block) => {
            let valueAtThisLocation = undefined;
            try {
                valueAtThisLocation = grid[block.subArrayIndex][block.subArrayElementIndex];
            } catch { }
            return (valueAtThisLocation == '1');
        })

        onlyBlocksThatHaveLand.forEach((block) => {
            addLocationToQueue(block);
        })
    }

    const conquerLand = () => {
        let locationFromQueue = dfsStack.pop();

        if (locationFromQueue != undefined) {
            expandFrontier(locationFromQueue);
        } else {
            numberOfIslands += 1;
            currentMode = 'find_land';
        }
    }

    const isThereLandAtThisLocation = () => {
        return grid[currentExplorationIndex.subArrayIndex][currentExplorationIndex.subArrayElementIndex] == '1';
    }

    const executeFindLand = () => {
        if (isThereLandAtThisLocation()) {

            // We have found land, so we start to conquer it
            addLocationToQueue(currentExplorationIndex);

            if (dfsStack.length > 0) {
                currentMode = 'conquer_land';
            } else {
                // This is not new land
                moveToNextLocation()
            }
        } else {
            // We have not found land, so we..
            moveToNextLocation()
        }
    }

    while (continueMainLoop) {

        if (currentMode == 'find_land') {
            executeFindLand();
        } else {
            conquerLand();
        }

    }

    return numberOfIslands;
}