Register for our webinar

How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

Count Islands Problem

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.

{
"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).
*/

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).
*/

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) {
q.pop();

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:

{
"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 {
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) {
}
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) {
}
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) {
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) {
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) {
}
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) {
}
return argument;
}

public static TextWriter textWriter;

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

List<List<int>> matrix;
try {
matrix = input_list_list_int32(data["matrix"]);
} catch (Exception ex) {
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) {
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(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)}' \` +
}
output_int32(result);
output_write("\n");
process.stdout.write(output_string);
}

/**
* @param {list_list_int32} matrix
* @return {int32}
*/
function count_islands(matrix) {
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()
while (ok) {
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 => {
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 = {
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 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 {
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
matrix = input_list_list_int32(data['matrix'])
rescue => err
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}' " +
end
output_int32(result)
print("\n")
end

# @param {list_list_int32} matrix
# @return {int32}
def count_islands(matrix)
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:
matrix = input_list_list_int32(data['matrix'])
except Exception as ex:
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__}" '
output_int32(result)
sys.stdout.write('\n')

def count_islands(matrix):
"""
Args:
matrix(list_list_int32)
Returns:
int32
"""
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) {
}
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) {
}
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) {
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 {
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 << 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) {
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;
}

/*
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) {
return 0;
}

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Count Islands Problem

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.

{
"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).
*/

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).
*/

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) {
q.pop();

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:

{
"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 {
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) {
}
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) {
}
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) {
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) {
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) {
}
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) {
}
return argument;
}

public static TextWriter textWriter;

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

List<List<int>> matrix;
try {
matrix = input_list_list_int32(data["matrix"]);
} catch (Exception ex) {
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) {
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(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)}' \` +
}
output_int32(result);
output_write("\n");
process.stdout.write(output_string);
}

/**
* @param {list_list_int32} matrix
* @return {int32}
*/
function count_islands(matrix) {
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()
while (ok) {
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 => {
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 = {
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 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 {
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
matrix = input_list_list_int32(data['matrix'])
rescue => err
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}' " +
end
output_int32(result)
print("\n")
end

# @param {list_list_int32} matrix
# @return {int32}
def count_islands(matrix)
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:
matrix = input_list_list_int32(data['matrix'])
except Exception as ex:
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__}" '
output_int32(result)
sys.stdout.write('\n')

def count_islands(matrix):
"""
Args:
matrix(list_list_int32)
Returns:
int32
"""
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) {
}
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) {
}
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) {
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 {
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 << 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) {
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;
}

/*
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) {