Use a depth first to traverse a matrix

Question

Problem

You are given a two-dimensional array (matrix) of potentially unequal height and width containing only 0s and 1s. Each 0 represents land, and each 1 represents part of a river. A river consists of any number of 1s that are either horizontally or vertically adjacent (but not diagonally adjacent). The number of adjacent 1s forming a river determine its size. Write a function that returns an array of the sizes of all rivers represented in the input matrix. Note that these sizes do not need to be in any particular order.

Input 
[
[1,0,0,1,0],
[1,0,1,0,0],
[0,0,1,0,1],
[1,0,1,0,1],
[1,0,1,1,0],
]

Output [1,2,2,2,5]

My Approach

After evaluating the problem i felt like this should be done using a graph traversal like algorithm maybe depth first search. So that is exactly what i do .

I traverse the matrix from top left and see if the value is visited and if it is not then and if the value is 1 then i traverse all it's nodes and keep a counter to keep size of the river. In the end i update an array list with the total river size.

For some reason my result is not correct and i am not sure what i did wrong. I hand traced my code too but can't figure out the issue.

My Code

import java.util.ArrayList;

class Program {
  public static ArrayList<Integer> riverSizes(int[][] matrix) {
    ArrayList<Integer> result = new ArrayList<Integer>();
        boolean [][] visitStatus = new boolean [matrix.length][matrix[0].length];

        for(int row = 0; row<matrix.length; row++){
            for(int col = 0; col<matrix.length; col++){
                int count = 0;
                count = traverseMatrix(row,col,matrix,visitStatus,count);
                result.add(count);
            }
        }
        return result;
  }

    public static int traverseMatrix(int row, int col, int [][] matrix, boolean [][] visitStatus, int count){
        if(visitStatus[row][col] == true){
            return count;
        }else if(matrix[row][col] == 0){
            visitStatus[row][col] = true;
            return count;
        }else{
            count++;
            visitStatus[row][col] = true;
            if(isValid(row,col-1,matrix)){
                return traverseMatrix(row,col-1,matrix,visitStatus,count);
            }
            if(isValid(row,col+1,matrix)){
                return traverseMatrix(row,col+1,matrix,visitStatus,count);
            }
            if(isValid(row-1,col,matrix)){
                return traverseMatrix(row-1,col,matrix,visitStatus,count);
            }
            if(isValid(row+1,col,matrix)){
                return traverseMatrix(row+1,col,matrix,visitStatus,count);
            }
        }
        return count;
    }

    public static boolean isValid(int row, int col,int[][] matrix){
        return (row >= 0 && row < matrix.length) && (col >= 0 && col < matrix[0].length);
    }
}

Answer 1

My solution is written in C#, but it's similar to Java:

You can replace List with ArrayList

Code:

        public static List<int> RiverSizes(int[,] matrix)
        {
            var sizes = new List<int>();
            bool[,] visited = new bool[matrix.GetLength(0), matrix.GetLength(1)];

            for (int row = 0; row < matrix.GetLength(0); row++)
                for (int col = 0; col < matrix.GetLength(1); col++)
                    if (visited[row, col])
                        continue;
                    else
                        Traverse(matrix, row, col, visited, sizes);
           return sizes;
        }

        public static void Traverse(int[,] matrix, int row, int col, bool[,] visited, List<int> sizes)
        {
            int currentSize = 0;
            var toExplore = new List<int[]>
            {
                new int[] { row, col }
            };

            while (toExplore.Count > 0)
            {
                var current = toExplore[^1];
                toExplore.RemoveAt(toExplore.Count - 1);
                row = current[0];
                col = current[1];

                if (visited[row, col])
                    continue;

                visited[row, col] = true;

                if (matrix[row, col] == 0)
                    continue;

                currentSize++;

                foreach (int[] item in GetNeighbours(matrix, row, col, visited))
                    toExplore.Add(item);
            }

            if (currentSize > 0)
                sizes.Add(currentSize);

        }

        public static List<int[]> GetNeighbours(int[,] matrix, int row, int col, bool[,] visited)
        {
            List<int[]> neighbours = new List<int[]>();

            if (row > 0 && !visited[row - 1, col])
                neighbours.Add(new int[] { row - 1, col });

            if (row < matrix.GetLength(0) - 1 && !visited[row + 1, col])
                neighbours.Add(new int[] { row + 1, col });

            if (col > 0 && !visited[row, col - 1])
                neighbours.Add(new int[] { row, col - 1 });

            if (col < matrix.GetLength(1) - 1 && !visited[row, col + 1])
                neighbours.Add(new int[] { row, col + 1 });
            return neighbours;
        }

I hope it helps ^-^

Answer 2

you are given a two-dimensional array (matrix) of potentially unequal height and width 

But you are doing the operation for always same size of matrix both in height and width

for(int row = 0; row<matrix.length; row++){ 
    for(int col = 0; col<matrix.length; col++){ .. }}

you should use the dimension like following way, rest of the things are enough well I guess ..

  for(int row = 0; row<matrix.length; row++){ 
    for(int col = 0; col<matrix[row].length; col++){ .. }}

and the changes need to apply in function 'isValid' also

public static boolean isValid(int row, int col,int[][] matrix){
    return (row >= 0 && row < matrix.length) && (col >= 0 && col < matrix[row].length);
}

Answer 3

In addition to @OleksandrPyrohov's answer, also check if the current cell is visited already before calling traverseMatrix :

public static ArrayList<Integer> riverSizes(int[][] matrix) {
    ArrayList<Integer> result = new ArrayList<Integer>();
        boolean [][] visitStatus = new boolean [matrix.length][matrix[0].length];

        for(int row = 0; row<matrix.length; row++){
            for(int col = 0; col<matrix.length; col++){
                if ( !visitStatus[row][col] ) {
                   int count = 0;
                   count = traverseMatrix(row,col,matrix,visitStatus,count);
                   result.add(count);
                }
            }
        }
        return result;
  }

Answer 4

Convert count to a local variable and accumulate it:

static int traverseMatrix(int row, int col, int[][] matrix, boolean[][] visitStatus) {
    if (visitStatus[row][col] || matrix[row][col] == 0) {
        return 0;
    }
    visitStatus[row][col] = true;
    int count = 1;
    if (isValid(row, col - 1, matrix)) {
        count += traverseMatrix(row, col - 1, matrix, visitStatus);
    }
    ...
    return count;
}