Number of Islands

🇷🇺 Название: Количество островов
LeetCode: number-of-islands
Временная сложность: O(n*m)
Пространственная сложность: O(n*m)

Решение

from typing import List  


class Solution:  
    def numIslands(self, grid: List[List[str]]) -> int:  
        if not grid:  
            return 0  

        rows, cols = len(grid), len(grid[0])  
        count = 0  

        def dfs(r, c):  
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':  
                return  
            grid[r][c] = '0'  
            dfs(r + 1, c)  
            dfs(r - 1, c)  
            dfs(r, c + 1)  
            dfs(r, c - 1)  

        for m in range(rows):  
            for n in range(cols):  
                if grid[m][n] == '1':  
                    dfs(m, n)  
                    count += 1  

        return count

🇺🇸 Условие

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

🇷🇺 Условие

Примеры

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3

{
  "examples": [
    {
      "input": {
        "grid": [
          ["1","1","1","1","0"],
          ["1","1","0","1","0"],
          ["1","1","0","0","0"],
          ["0","0","0","0","0"]
        ]
      },
      "output": 1
    },
    {
      "input": {
        "grid": [
          ["1","1","0","0","0"],
          ["1","1","0","0","0"],
          ["0","0","1","0","0"],
          ["0","0","0","1","1"]
        ]
      },
      "output": 3
    }
  ]
}

Ограничения

• m == grid.length
• n == grid[i].length
• \(1 \leq m, n \leq 300\)
• grid[i][j] is '0' or '1'.

Потребление ресурсов

⏱ Time complexity: O(n*m)

• Каждая ячейка посещается ровно один раз

Итог: O(n*m)

🧠 Space complexity: O(n*m)

• В худшем случае (всё земля) стек рекурсии = O(n * m)

Итог: O(n*m)

medium array depth-first-search breadth-first-search union-find matrix

---

Metadata

• title_rus: Количество островов
• difficulty: Medium
• leetcode_url: https://leetcode.com/problems/number-of-islands/
• topics: ['Array', 'Depth-First Search', 'Breadth-First Search', 'Union Find', 'Matrix']
• time: O(n*m)
• space: O(n*m)
• grind75: True
• tags: ['Array', 'Breadth-First Search', 'Depth-First Search', 'Matrix', 'Medium', 'Union Find', 'problem']
• git_revision_date_localized: 5 июля 2025 г.
• git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_revision_date_localized_tag:
• git_revision_date_localized_raw_date: 5 июля 2025 г.
• git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_revision_date_localized_raw_iso_date: 2025-07-05
• git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_revision_date_localized_raw_timeago:
• git_revision_date_localized_raw_custom: 05. июля 2025
• git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_site_revision_date_localized_tag:
• git_site_revision_date_localized: 5 июля 2025 г.
• git_site_revision_date_localized_raw_date: 5 июля 2025 г.
• git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_site_revision_date_localized_raw_iso_date: 2025-07-05
• git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_site_revision_date_localized_raw_timeago:
• git_site_revision_date_localized_raw_custom: 05. июля 2025