D
DevExCode

LeetCode 1254: Number of Closed Islands Solution

Master LeetCode problem 1254 (Number of Closed Islands), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can perform a Depth First Search (DFS) traversal on the grid to identify closed islands. We will start DFS from each cell that is a land (0) and not already visited. While performing DFS, we mark visited cells and also check if the island is closed by ensuring that it is surrounded by water (1) from all sides.

  1. Iterate through each cell in the grid.
  2. If the cell is a land (0) and not visited, start DFS from that cell.
  3. In DFS, mark the current cell as visited and recursively explore its neighboring cells.
  4. While exploring neighbors, ensure that the indices are within the bounds of the grid and the neighbor cell is also a land (0).
  5. If any neighbor is outside the grid bounds, it means the island is not closed.
  6. After DFS traversal, if the island is closed, increment the count of closed islands.

Time Complexity: O(M * N) where M is the number of rows and N is the number of columns in the grid. Space Complexity: O(M * N) due to the recursive DFS stack.

Solution Code

class Solution {
    public int closedIsland(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int closedIslands = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0 && isClosedIsland(grid, i, j)) {
                    closedIslands++;
                }
            }
        }

        return closedIslands;
    }

    private boolean isClosedIsland(int[][] grid, int i, int j) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (i < 0 || j < 0 || i >= rows || j >= cols) {
            return false;
        }

        if (grid[i][j] == 1) {
            return true;
        }

        grid[i][j] = 1;
        boolean top = isClosedIsland(grid, i - 1, j);
        boolean bottom = isClosedIsland(grid, i + 1, j);
        boolean left = isClosedIsland(grid, i, j - 1);
        boolean right = isClosedIsland(grid, i, j + 1);

        return top && bottom && left && right;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 1254 (Number of Closed Islands)?

This page provides optimized solutions for LeetCode problem 1254 (Number of Closed Islands) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1254 (Number of Closed Islands)?

The time complexity for LeetCode 1254 (Number of Closed Islands) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1254 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1254 in Java, C++, or Python.

Back to LeetCode Solutions