Counting the number of islands is a commonly asked graph interview question at tech interviews. Here, we show you how to solve it using DFS and BFS.

Count Islands Problem Statement

Given a two-dimensional matrix of 0s and 1s, find the number of islands.

An island is a group of connected 1s or a standalone 1. A cell in the matrix can be connected to up to 8 neighbors: 2 vertical, 2 horizontal and 4 diagonal.

Example

{
"matrix": [
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
}

Output:

‍
5

Notes

Constraints:

The problem is easy but there is one very important thing to learn. We recommend reading through the whole editorial even if your solution passed all tests.

Count Islands Solution 1: Depth First Search

Treat the matrix like a graph and do a simple DFS or BFS.

We are not allowed to use a visited matrix, but we can modify the input matrix itself! When a node is visited, change its value from 1 to 0.

Time Complexity

O(n * m).

Time complexity of BFS or DFS is O(V + E), in our case it will be O(n * m + 8 * n * m) that is O(n * m).

Auxiliary Space Used

O(n * m) for the DFS solution. The space is used by the call stack because the solution is recursive. If we had used an iterative DFS implementation, we would use a stack and same O(n * m) auxiliary space for that.

Consider the worst case for DFS:

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

Code For Count Islands Solution 1: Depth First Search

/*
Asymptotic complexity in terms of \`n\` and \`m\` dimensions of the input matrix:
* Time: O(n * m).
* Auxiliary space: O(n * m).
* Total space: O(n * m).
*/

// All 8 directions. Consider as pair: {add_r[i], add_r[i]}.
const int add_r[8] = {0, -1, -1, -1, 0, 1, 1, 1};
const int add_c[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

// Note that we are passing matrix by reference. Passing by value will not work because we are doing
// modifications in matrix. So either pass by reference or use global variable.
void dfs(int row, int column, vector<vector<int>> &matrix) {
   matrix[row][column] = 0;
   for (int i = 0; i < 8; i++) {
       // Try to visit all 8 neighbours.
       int new_row = row + add_r[i];
       int new_column = column + add_c[i];

       // Out of the matrix.
       if (new_row < 0 || new_row >= matrix.size() || new_column < 0 || new_column >= matrix[0].size()) {
           continue;
       }

       if (matrix[new_row][new_column]) {
           dfs(new_row, new_column, matrix);
       }
   }
}

int count_islands(vector<vector<int>> &matrix) {
   int islands = 0;
   int n = matrix.size();
   int m = matrix[0].size();

   for (int i = 0; i < n; i++) {
       for (int j = 0; j < m; j++) {
           // When we find unvisited node, visit it and visit all the reachable nodes.
           if (matrix[i][j]) {
               islands++;
               dfs(i, j, matrix);
           }
       }
   }
   return islands;
}

Count Islands Solution 2: Breadth First Search

DFS would make almost n * m nested recursive calls; that takes O(n * m) space.

BFS solution, on the other hand, uses just O(max(n, m)) of auxiliary space.

The worst-case for BFS is similar to that of DFS, where all entries of matrix are 1. Consider the worst-case scenario, at some point of time all the nodes of the last row and last column will be in the queue. The queue will then take O(n + m) = O(max(n, m)) space.

This difference in used space between the two algorithms can affect performance in some real life cases.

Space Complexity

O(n * m), due to input size and auxiliary space used.

Code For Count Islands Solution 2: Breadth First Search

/*
Asymptotic complexity in terms of \`n\` and \`m\` dimensions of the input matrix:
* Time: O(n * m).
* Auxiliary space: O(max(n, m)).
* Total space: O(n * m).
*/

// All 8 directions. Consider as pair: {add_r[i], add_r[i]}.
const int add_r[8] = {0, -1, -1, -1, 0, 1, 1, 1};
const int add_c[8] = {-1, -1, 0, 1, 1, 1, 0, -1};

void bfs(int row, int column, vector<vector<int>> &matrix) {
   queue<pair<int, int>> q;
   q.push({row, column});
   matrix[row][column] = 0;

   while (q.empty() == false) {
       pair<int, int> head = q.front();
       q.pop();
       int current_row = head.first;
       int current_column = head.second;

       for (int i = 0; i < 8; i++) {
           // Try to visit all 8 neighbours.
           int new_row = current_row + add_r[i];
           int new_column = current_column + add_c[i];

           // Out of the matrix.
           if (new_row < 0 || new_row >= matrix.size() || new_column < 0 || new_column >= matrix[0].size()) {
               continue;
           }

           if (matrix[new_row][new_column]) {
               /*
               We could have marked as 0 when we pop-up the element from the queue and not here.
               This will also give correct answer, but that is not the correct way! If we do
               that, same element will be pushed multiple times in the queue (that will increase
               running time and queue size unnecessarily)! Take some examples and try to figure
               it out.
               */
               matrix[new_row][new_column] = 0;
               q.push({new_row, new_column});
           }
       }
   }
}

int count_islands(vector<vector<int>> &matrix) {
   int islands = 0;
   int n = matrix.size();
   int m = matrix[0].size();

   for (int i = 0; i < n; i++) {
       for (int j = 0; j < m; j++) {
           // When we find unvisited node, visit it and visit all the reachable nodes.
           if (matrix[i][j]) {
               islands++;
               bfs(i, j, matrix);
           }
       }
   }
   return islands;
}

We hope that these solutions to counting islands have helped you level up your coding skills. You can expect graph problems like counting islands at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 17 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

‍To learn more, register for the FREE webinar.
         {
"matrix": [
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
}

{
"matrix": [
[1, 1, 0],
[1, 1, 0],
[0, 0, 0]
]
}

{
"matrix": [
[0]
]
}

package main

import (
   "bufio"
   "bytes"
   "container/heap"
   "container/list"
   "container/ring"
   "fmt"
   "io"
   "math"
   "math/rand"
   "os"
   "encoding/json"
   "strconv"
   "strings"
   "sort"
   "unicode"
)

var _ = bufio.ScanBytes
var _ = bytes.Count
var _ = heap.Init
var _ = list.New
var _ = ring.New
var _ = io.EOF
var _ = math.Pow
var _ = rand.Int
var _ = strconv.Atoi
var _ = strings.TrimRight
var _ = sort.Slice
var _ = unicode.IsDigit

                   func output_int32(argument int)  {
   output_write(strconv.Itoa(argument))
}


func input_int32(data interface{}) int {
   argument:= int(data.(float64))
   return argument
}


func input_list_int32(data interface{}) [] int {
   json_array:= data.([]interface{})
   json_array_length:= len(json_array)
   var argument [] int
   for i:= 0; i < int(json_array_length); i++ {
       argument = append(argument, input_int32(json_array[i]))
   }
   return argument
}


func input_list_list_int32(data interface{}) [] [] int {
   json_array:= data.([]interface{})
   json_array_length:= len(json_array)
   var argument [] [] int
   for i:= 0; i < int(json_array_length); i++ {
       argument = append(argument, input_list_int32(json_array[i]))
   }
   return argument
}



func output_write(x string) {
   output_string.WriteString(x)
}

var output_string strings.Builder

func main() {

   var matrix [] [] int
   var data map[string]interface{}
   dec:= json.NewDecoder(os.Stdin)
   dec.Decode(&data)
   matrix = input_list_list_int32(data["matrix"])
   var original_out = os.Stdout
   os.Stdout = os.Stderr
   result:= count_islands(matrix)
   os.Stdout = original_out
   output_int32(result)
   output_write("\n")
   fmt.Print(output_string.String())
}

func count_islands(matrix [] [] int) int {
   // Write your code here.
   return 0
}

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
import org.json.*;


class Solution {

                   }

class Result {

   static void output_int32(Integer argument) {
       output_string.append(argument);
   }


   static Integer input_int32(Object data) {
       Integer argument = (Integer) data;
       return argument;
   }


   static ArrayList<Integer> input_list_int32(Object data) {
       JSONArray json_array = (JSONArray) data;
       ArrayList argument = new ArrayList<Integer>();
       for (Object json_array_item: json_array) {
           argument.add(input_int32(json_array_item));
       }
       return argument;
   }


   static ArrayList<ArrayList<Integer>> input_list_list_int32(Object data) {
       JSONArray json_array = (JSONArray) data;
       ArrayList argument = new ArrayList<ArrayList<Integer>>();
       for (Object json_array_item: json_array) {
           argument.add(input_list_int32(json_array_item));
       }
       return argument;
   }


   private static final DecimalFormat float_formatter = new DecimalFormat("0.00");
   private static final StringBuilder output_string = new StringBuilder();
   public static void main(String[] args) throws Exception {

       ArrayList<ArrayList<Integer>> matrix;
       try {
           ByteArrayOutputStream json_string = new ByteArrayOutputStream();
           byte[] buffer = new byte[1024];
           for (int length; (length = System.in.read(buffer)) != -1; ) {
               json_string.write(buffer, 0, length);
           }
           JSONObject data = new JSONObject(json_string.toString("UTF-8"));
           matrix = input_list_list_int32(data.get("matrix"));
       } catch (Exception ex) {
           System.err.println("reading-input-failed-json");
           ex.printStackTrace();
           throw ex;
       }

       PrintStream original_out = System.out;
       System.setOut(System.err);
       Integer result = Solution.count_islands(matrix);
       System.setOut(original_out);
       output_int32(result);
       output_string.append('\n');
       System.out.print(output_string.toString());
   }



   static Integer count_islands(ArrayList<ArrayList<Integer>> matrix) {
       // Write your code here.
       return 0;
   }

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Json;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;


class Solution {

                   }
class Result {


   public static void output_int32(int argument) {
       textWriter.Write(argument);
   }


   public static int input_int32(Object data) {
       int argument = (int) (JsonValue) data;
       return argument;
   }


   public static List<int> input_list_int32(Object data) {
       JsonArray json_array = (JsonArray) data;
       List<int> argument = new List<int>();
       foreach (Object json_array_item in json_array) {
           argument.Add(input_int32(json_array_item));
       }
       return argument;
   }


   public static List<List<int>> input_list_list_int32(Object data) {
       JsonArray json_array = (JsonArray) data;
       List<List<int>> argument = new List<List<int>>();
       foreach (Object json_array_item in json_array) {
           argument.Add(input_list_int32(json_array_item));
       }
       return argument;
   }


   public static TextWriter textWriter;

   public static void Main(string[] args) {
       textWriter = new StreamWriter(Console.OpenStandardOutput());


       List<List<int>> matrix;
       try {
           JsonValue data = JsonValue.Load(new StreamReader(Console.OpenStandardInput()));
           matrix = input_list_list_int32(data["matrix"]);
       } catch (Exception ex) {
           Console.Error.WriteLine("reading-input-failed-json");
           Console.Error.WriteLine(ex.StackTrace);
           throw ex;
       }

       TextWriter original_out = Console.Out;
       Console.SetOut(Console.Error);
       int result = Solution.count_islands(matrix);
       Console.SetOut(original_out);
       output_int32(result);
       textWriter.Write('\n');

       textWriter.Flush();
       textWriter.Close();
   }
}

   public static int count_islands(List<List<int>> matrix) {
       // Write your code here.
       return 0;
   }

'use strict';

const fs = require('fs');

function output_int32(argument) {
   output_write(\`\${argument}\`);
}


function input_int32(data) {
   const argument = parseInt(data);
   if (argument === undefined || isNaN(argument)) {
       throw TypeError();
   }
   return argument;
}


function input_list_int32(data) {
   const argument = [];
   for (let i = 0; i < data.length; i++) {
       argument.push(input_int32(data[i]));
   }
   return argument;
}


function input_list_list_int32(data) {
   const argument = [];
   for (let i = 0; i < data.length; i++) {
       argument.push(input_list_int32(data[i]));
   }
   return argument;
}


process.stdin.resume();
process.stdin.setEncoding('utf-8');

process.stdin.on('data', function(input_stdin) {
   input_string += input_stdin;
});

process.stdin.on('end', function() {
   main();
});

function output_write(x) {
   output_string += x;
}

let input_string = '';
let output_string = '';

function main() {

   var matrix;
   try {
       const data = JSON.parse(input_string);
       matrix = input_list_list_int32(data['matrix']);
   } catch (err) {
       process.stderr.write("reading-input-failed-json\n");
       process.stderr.write(err.stack);
       throw err;
   }

   const original_out = process.stdout.write;
   process.stdout.write = process.stderr.write.bind(process.stderr);
   const result = count_islands(matrix);
   process.stdout.write = original_out.bind(process.stdout);
   if (result === undefined) {
       throw \`Don't forget to return the answer from the function!\`;
   }
   if (typeof(result) !== 'number') {
       throw \`-------- You returned a value of type '\${typeof(result)}' \` +
                       \`instead of 'number'. --------\`;
   }
   output_int32(result);
   output_write("\n");
   process.stdout.write(output_string);
}

/**
* @param {list_list_int32} matrix
* @return {int32}
*/
function count_islands(matrix) {
   // Write your code here.
   return 0;
}
import java.io._
import java.math._
import java.security._
import java.text._
import java.util._
import java.util.concurrent._
import java.util.function._
import java.util.regex._
import java.util.stream._
import scala.collection.concurrent._
import scala.collection.immutable._
import scala.collection.mutable._
import scala.concurrent._
import scala.io._
import scala.jdk.CollectionConverters._
import scala.math._
import scala.reflect._
import scala.sys._
import scala.util.matching._
import org.json._


object Solution {

                   }

object Main {

   def output_int32(argument: Int): Unit = {
       output_write(argument.toString)
   }


   def input_int32(data: Any): Int = {
       val argument = data.asInstanceOf[Int]
       return argument
   }


   def input_list_int32(data: Any): Array[Int] = {
       var json_array = data.asInstanceOf[JSONArray]
       val json_array_length = json_array.length()
       val argument = Array.ofDim[Int](json_array_length)
       for (i <- 0 until json_array_length) {
           argument(i) = input_int32(json_array.get(i))
       }
       return argument
   }


   def input_list_list_int32(data: Any): Array[Array[Int]] = {
       var json_array = data.asInstanceOf[JSONArray]
       val json_array_length = json_array.length()
       val argument = Array.ofDim[Array[Int]](json_array_length)
       for (i <- 0 until json_array_length) {
           argument(i) = input_list_int32(json_array.get(i))
       }
       return argument
   }

   def output_write(x: String) = {
       output_string ++= x
   }

   val output_string = new StringBuilder("")

   def main(args: Array[String]) = {

       var matrix: Array[Array[Int]] = Array[Array[Int]]()
       try {
           var ok = true
           var json_string = new StringBuilder()
           val bufferedReader = new java.io.BufferedReader(new java.io.InputStreamReader(System.in))
           while (ok) {
               val line = bufferedReader.readLine()
               json_string = json_string.append(line)
               ok = line != null
           }
           var data = new JSONObject(json_string.toString)
           matrix = input_list_list_int32(data.get("matrix"))
       } catch {
           case ex: Exception => {
               System.err.println("reading-input-failed-json")
               ex.printStackTrace()
               throw ex
           }
       }
       val original_out = System.out
       System.setOut(System.err)
       val result = Solution.count_islands(matrix)
       System.setOut(original_out)
       output_int32(result)
       output_write("\n")
       System.out.print(output_string)
   }
}

   def count_islands(matrix: Array[Array[Int]]): Int = {
       // Write your code here.
       return 0
   }

import Foundation

                   func output_int32(argument: Int) -> () {
   output_write(x: String(argument))
}


func input_int32(data:Any) -> Int {
   let argument = (data as! NSNumber).intValue
   return argument
}


func input_list_int32(data:Any) -> [Int] {
   let json_array = data as! [Any]
   var argument = [Int]()
   for json_array_item in json_array {
       argument.append(input_int32(data:json_array_item))
   }
   return argument
}


func input_list_list_int32(data:Any) -> [[Int]] {
   let json_array = data as! [Any]
   var argument = [[Int]]()
   for json_array_item in json_array {
       argument.append(input_list_int32(data:json_array_item))
   }
   return argument
}



func output_write(x: String) -> () {
   output_string += x
}

struct EncodableString {
   let s: String
}

extension EncodableString : Encodable {
   func encode(to encoder: Encoder) throws {
       var container = encoder.singleValueContainer()
       try container.encode(s)
   }
}

var output_string = ""
let encoder = JSONEncoder()
encoder.outputFormatting = .withoutEscapingSlashes


var matrix: [[Int]]
let file_content = FileHandle.standardInput.readDataToEndOfFile()
let data = try JSONSerialization.jsonObject(with: file_content, options: []) as! [String: Any]
matrix = input_list_list_int32(data: data["matrix"]!)
var original_out = stdout
stdout = stderr
let result = count_islands(matrix: matrix)
stdout = original_out
output_int32(argument: result)
output_write(x: "\n")
print(output_string, terminator:"")


func count_islands(matrix: [[Int]]) -> Int {
   // Write your code here.
   return 0
}

#!/bin/ruby


require 'json'
require 'stringio'

def output_int32(argument)
   print(argument)
end


def input_int32(data)
   argument = Integer(data)
   return argument
end


def input_list_int32(data)
   json_array_length = data.length().to_i()
   argument = Array.new(json_array_length)
   json_array_length.times() do |i|
       argument[i] = input_int32(data[i])
   end
   return argument
end


def input_list_list_int32(data)
   json_array_length = data.length().to_i()
   argument = Array.new(json_array_length)
   json_array_length.times() do |i|
       argument[i] = input_list_int32(data[i])
   end
   return argument
end


if __FILE__ == \$0
   begin
       data = JSON.load(ARGF.read())
       matrix = input_list_list_int32(data['matrix'])
   rescue => err
       STDERR.puts("reading-input-failed-json")
       STDERR.puts(err)
       raise err
   end

   original_out = \$stdout.dup
   \$stdout.reopen(\$stderr.dup)
   result = count_islands(matrix)
   \$stdout.reopen(original_out)
   if result.nil?
       raise TypeError, "Don't forget to return the answer from the function!"
   end
   if not result.instance_of?(Integer)
       raise TypeError, "-------- You returned a value of type '#{result.class}' " +
                       "instead of 'Integer'. --------"
   end
   output_int32(result)
   print("\n")
end

# @param {list_list_int32} matrix
# @return {int32}
def count_islands(matrix)
   # Write your code here.
   return 0
end

#!/usr/bin/env python
import json
import math
import os
import random
import re
import sys
import traceback
from collections import deque

sys.setrecursionlimit(2000009)


def output_int32(argument):
   sys.stdout.write(f'{argument}')


def input_int32(data):
   argument = int(data)
   return argument


def input_list_int32(data):
   argument = []
   for json_array_item in data:
       argument.append(input_int32(json_array_item))
   return argument


def input_list_list_int32(data):
   argument = []
   for json_array_item in data:
       argument.append(input_list_int32(json_array_item))
   return argument


if __name__ == '__main__':
   try:
       data = json.load(sys.stdin)
       matrix = input_list_list_int32(data['matrix'])
   except Exception as ex:
       sys.stderr.write('reading-input-failed-json\n')
       traceback.print_exc()
       raise ex

   original_out = sys.stdout
   sys.stdout = sys.stderr
   result = count_islands(matrix)
   sys.stdout = original_out
   if result is None:
       raise TypeError("Don't forget to return the answer from the function!")
   if type(result) is not int:
       raise TypeError(f'-------- You returned a value of type "{type(result).__name__}" '
                       f'instead of "int". --------')
   output_int32(result)
   sys.stdout.write('\n')

def count_islands(matrix):
   """
   Args:
    matrix(list_list_int32)
   Returns:
    int32
   """
   # Write your code here.
   return 0

import java.io.*
import java.math.*
import java.security.*
import java.text.*
import java.util.*
import java.util.concurrent.*
import java.util.function.*
import java.util.regex.*
import java.util.stream.*
import java.util.stream.Collectors.joining
import java.util.stream.Collectors.toList
import org.json.*

                   fun output_int32(argument: Int): Unit {
   output_string.append(argument)
}


fun input_int32(data: Any): Int {
   val argument = data as Int
   return argument
}


fun input_list_int32(data: Any): ArrayList<Int> {
   val json_array = data as JSONArray
   var argument = arrayListOf<Int>()
   for (json_array_item: Any in json_array) {
       argument.add(input_int32(json_array_item))
   }
   return argument
}


fun input_list_list_int32(data: Any): ArrayList<ArrayList<Int>> {
   val json_array = data as JSONArray
   var argument = arrayListOf<ArrayList<Int>>()
   for (json_array_item: Any in json_array) {
       argument.add(input_list_int32(json_array_item))
   }
   return argument
}


val float_formatter: DecimalFormat = DecimalFormat("0.00")
val output_string = StringBuilder()
fun main(args: Array<String>) {

   var matrix: ArrayList<ArrayList<Int>>
   try {
       val json_string = ByteArrayOutputStream()
       val buffer = ByteArray(1024)
       var length: Int
       while (System.\`in\`.read(buffer).also { length = it } != -1) {
           json_string.write(buffer, 0, length)
       }
       val data = JSONObject(json_string.toString("UTF-8"))
       matrix = input_list_list_int32(data.get("matrix"))
   } catch (ex: Exception) {
       System.err.println("reading-input-failed-json")
       ex.printStackTrace()
       throw ex
   }

   val original_out: PrintStream = System.out
   System.setOut(System.err)
   val result = count_islands(matrix)
   System.setOut(original_out)
   output_int32(result)
   output_string.append('\n')
   System.out.print(output_string.toString())
}


fun count_islands(matrix: ArrayList<ArrayList<Int>>): Int {
   // Write your code here.
   return 0
}

#include <bits/stdc++.h>
#include <fcntl.h>
#include <unistd.h>
#include <nlohmann/json.hpp>

using json = nlohmann::json;
using namespace std;

                   void output_int32(int argument) {
   cout << argument;
}


int input_int32(json data) {
   int argument = data;
   return argument;
}


vector<int> input_list_int32(json data) {
   int json_array_length = (int) data.size();
   vector<int> argument(json_array_length);
   for (int i = 0; i < json_array_length; i++) {
       argument[i] = input_int32(data[i]);
   }
   return argument;
}


vector<vector<int>> input_list_list_int32(json data) {
   int json_array_length = (int) data.size();
   vector<vector<int>> argument(json_array_length);
   for (int i = 0; i < json_array_length; i++) {
       argument[i] = input_list_int32(data[i]);
   }
   return argument;
}


int main() {

   vector<vector<int>> matrix;
   try {
       string json_string = "";
       string line;
       while (getline(cin, line)) {
           json_string+=line;
       }
       auto data = json::parse(json_string);
       matrix = input_list_list_int32(data["matrix"]);
   } catch(exception &ex) {
       cerr << "reading-input-failed-json" << endl;
       cerr << ex.what() << endl;
       throw ex;
   }
   dup2(1, 3);
   dup2(2, 1);

   int result = count_islands(matrix);

   fflush(stdout);
   dup2(3, 1);

   output_int32(result);
   cout << "\n";

   return 0;
}


int count_islands(vector<vector<int>> &matrix) {
   // Write your code here.
   return 0;
}

#include <assert.h>
#include <ctype.h>
#include <fcntl.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <cjson/cJSON.h>

typedef struct list list ;

struct list {
   int *items;
   int length;
};

typedef struct list_list list_list ;

struct list_list {
   list **items;
   int length;
};

                   void output_int32(int argument) {
   printf("%d", argument);
}


int input_int32(cJSON *data) {
   int argument = data->valueint;
   return argument;
}


list *input_list_int32(cJSON *data) {
   // cJSON_Array: \`child\` points to a linked list of cJSON items that represent values.
   cJSON *json_array_item = data->child; // First item in the array.
   list *argument = malloc(sizeof(list));

   while (json_array_item != NULL) {
       argument->length++;
       json_array_item = json_array_item->next;
   }
   argument->items = malloc(argument->length * sizeof(int));

   json_array_item = data->child; // Back to the first item in the array.
   for (int i = 0; i < argument->length; i++) {
       argument->items[i] = input_int32(json_array_item);
       json_array_item = json_array_item->next;
   }
   return argument;
}


list_list *input_list_list_int32(cJSON *data) {
   // cJSON_Array: \`child\` points to a linked list of cJSON items that represent values.
   cJSON *json_array_item = data->child; // First item in the array.
   list_list *argument = malloc(sizeof(list_list));

   while (json_array_item != NULL) {
       argument->length++;
       json_array_item = json_array_item->next;
   }
   argument->items = malloc(argument->length * sizeof(list *));

   json_array_item = data->child; // Back to the first item in the array.
   for (int i = 0; i < argument->length; i++) {
       argument->items[i] = input_list_int32(json_array_item);
       json_array_item = json_array_item->next;
   }
   return argument;
}


int main() {

   list_list *matrix;
   size_t alloc_length = 1024;
   size_t cursor = 0;
   signed char *json_string = (signed char *) malloc(alloc_length);
   signed char ch;
   while ((ch = getchar()) != EOF) {
       if (cursor >= alloc_length - 1) {
           alloc_length <<= 1;
           json_string = realloc(json_string, alloc_length);
       }
       json_string[cursor++] = ch;
   }
   json_string[cursor] = '\0';
   cursor++;
   json_string = realloc(json_string, cursor);
   cJSON *data = cJSON_Parse(json_string);
   matrix = input_list_list_int32(cJSON_GetObjectItemCaseSensitive(data, "matrix"));

   dup2(1, 3);
   dup2(2, 1);

   int result = count_islands(matrix);

   fflush(stdout);
   dup2(3, 1);

   output_int32(result);
   printf("\n");

   return 0;
}

/*
For your reference:
typedef struct list list ;

struct list {
   int *items;
   int length;
};

typedef struct list_list list_list ;

struct list_list {
   list **items;
   int length;
};
*/
int count_islands(list_list *matrix) {
   // Write your code here.
   return 0;
}