How to handle List of list Integer and find neighbours?

Question

I am currently trying to solve a problem where the input should be as following

int hours(int rows, int columns, List<List<Integer> > grid)

Where list grid is a Matrix of 0 and 1 ( 0 means not complete , 1 means complete ) as following:

0 1 1 0 1 
0 1 0 1 0 
0 0 0 0 1 
0 1 0 0 0 

Each value represent a machine in a network sending files to each other, So if the value is "1" then this node is able to send the files to ALL NEIGHBORS (Diagonal ones does not count only up/down/right/left).The issue is that once a 0 becomes a 1 ( affected by the neighbor cell ) it cannot send the file to any other neighbor before 1 HOUR.

The goal of the problem is to return how many hours shall it take before all the nodes receive the files? ( in other words all the Matrix becomes 1. Considering Run time complexity

For visual explanation: ( After the first hour this should be the state of the matrix which is considered as an iteration):

 1 1 1 1 1
 1 1 1 1 1
 0 1 0 1 1
 1 1 1 0 1

So, I followed an approach where I loop over the matrix looking in the provided grid and appending values in a temporary array ( as I don't know how to update or append the list values inside the main List). Then once the row index has reached the max i add 1 hour to an int variable and add values to the main grid.

I know the below code is not still working/complete and may have syntax mistakes but you get the idea and the approach.

My Question is, Is there any easier and efficient method than mine?? I also found a solution here But that only works with 2D arrays if my idea is worth it. However, wouldn't these 4 nested loop mess up the complexity of the code?

    List<List<Integer>> grid2 = grid1;
    boolean received= false;
    int hours=0;
    int rows_Temp = 0 ;
    int columsTemp = 0 ;
    int[][] grid2 = null ;
    while(rows_Temp<rows&&!received)
    {
        if(rows_Temp==rows-1)
        { 
            rows_Temp=0;
        }
        if(rows_Temp==0) 
        {
            //create an array with the grid dimention
            grid2= new int[rows][columns];
        }
        //manage top left corner
        if(rows_Temp==0 && columsTemp == 0 ) 
        {
            //find right & down
            int center= grid.get(rows_Temp).get(columsTemp);
            int right = grid.get(rows_Temp).get(columsTemp+1);
            int down  = grid.get(rows_Temp+1).get(columsTemp);


            if(center==1)
            {
                if(right==0)
                {
                    grid2[rows_Temp][columsTemp+1] = 1;
                }
                if(down==0)
                {
                    grid2[rows_Temp+1][columsTemp]=1;
                }
            }
        }
        //manage top right corner
        else if(rows_Temp==0 && columsTemp == columns-1)
        {
            //find left and down
            int center= grid.get(rows_Temp).get(columsTemp);
            int left = grid.get(rows_Temp).get(columsTemp-1);
            int down  = grid.get(rows_Temp+1).get(columsTemp);

            if(center==1)
            {
                if(left==0)
                {
                    grid2[rows_Temp][columsTemp-1] = 1;
                }
                if(down==0)
                {
                    grid2[rows_Temp+1][columsTemp]=1;
                }
            }
        }
        //mange down left corner of the array
        else if(rows_Temp==rows-1 && columsTemp == 0)
        {
            //find up and right
            int center= grid.get(rows_Temp).get(columsTemp);
            int right = grid.get(rows_Temp).get(columsTemp+1);
            int up  = grid.get(rows_Temp-1).get(columsTemp);

            if(center==1)
            {
                if(right==0)
                {
                    grid2[rows_Temp][columsTemp+1] = 1;
                }
                if(up==0)
                {
                    grid2[rows_Temp-1][columsTemp]=1;
                }
            }
        }
        //manage down right corner
        else if(rows_Temp==rows-1 && columsTemp == columns-1)
        {
            //find left and up
            int center= grid.get(rows_Temp).get(columsTemp);
            int left = grid.get(rows_Temp).get(columsTemp-1);
            int up  = grid.get(rows_Temp-1).get(columsTemp);

            if(center==1)
            {
                if(left==0)
                {
                    grid2[rows_Temp][columsTemp-1] = 1;
                }
                if(up==0)
                {
                    grid2[rows_Temp-1][columsTemp]=1;
                }
            }
        }
        //manage left sides but not corners
        else if(rows_Temp!=0&& rows_Temp!=rows-1&& columsTemp==0)
        {
            int center= grid.get(rows_Temp).get(columsTemp);
            int right = grid.get(rows_Temp).get(columsTemp+1);
            int up  = grid.get(rows_Temp-1).get(columsTemp);
            int down  = grid.get(rows_Temp+1).get(columsTemp);

            if(center==1)
            {
                if(right==0)
                {
                    grid2[rows_Temp][columsTemp+1] = 1;
                }
                if(up==0)
                {
                    grid2[rows_Temp-1][columsTemp]=1;
                }
                if(down==0)
                {
                    grid2[rows_Temp+1][columsTemp]=1;
                }
            }  
        }    

        if(columsTemp==columns-1)
        {
            columsTemp=0;
            rows_Temp++;
            System.out.println();
        }
        else
        {
            columsTemp++;
        }


    }
    System.out.println("------------");
    return 0 ;
}

Answer 1

If you're allowed to update grid, use grid.get(y).get(x) to check the grid and grid.get(y).set(x, value) to update the grid. If you're not allowed to update the grid, start by copying the values into a int[][] 2D array, then use that instead in the solution below.

Scan the grid for 0 values, and add the coordinates to a Queue<Point>, e.g. an ArrayDeque<Point>, where Point is an object with two int fields, e.g. the java.awt.Point class.

We do that to ensure good performance, with run time complexity as O(nm), where n and m are the width and height of the grid.

Start a loop with i = 1. In the loop, iterate the queue. If the point has a neighboring value equal to i, set the points value to i + 1, otherwise add the point to a second queue. At the end, replace the first queue with the second queue, increase i by 1 and do it again, until the queue is empty.

The result is a progression of the 2D matrix like this:

0 1 1 0 1   →   2 1 1 2 1   →   2 1 1 2 1   →   2 1 1 2 1
0 1 0 0 0   →   2 1 2 0 2   →   2 1 2 3 2   →   2 1 2 3 2
0 0 0 0 1   →   0 2 0 2 1   →   3 2 3 2 1   →   3 2 3 2 1
0 0 0 1 0   →   0 0 2 1 2   →   0 3 2 1 2   →   4 3 2 1 2

The highest value in the matrix is 4, so the answer is 3 hours, one less than highest value.

---

UPDATE

Here is the code, which copies the input to a 2D array, and lowers the values by 1, since it makes more sense that way.

static int hours(int rows, int columns, List<List<Integer>> grid) {
    // Build hourGrid, where value is the number of hours until the
    // node can send, with MAX_VALUE meaning the node cannot send.
    // Also build queue of nodes that cannot send.
    int[][] hourGrid = new int[rows][columns];
    Queue<Point> pending = new ArrayDeque<>();
    for (int y = 0; y < rows; y++) {
        for (int x = 0; x < columns; x++) {
            if (grid.get(y).get(x) == 0) {
                hourGrid[y][x] = Integer.MAX_VALUE;
                pending.add(new Point(x, y));
            }
        }
    }

    // Keep iterating the queue until all pending nodes can send.
    // Each iteration adds 1 hour to the total time.
    int hours = 0;
    for (; ! pending.isEmpty(); hours++) {
        // Check all pending nodes if they can receive data
        Queue<Point> notYet = new ArrayDeque<>();
        for (Point p : pending) {
            if ((p.x > 0           && hourGrid[p.y][p.x - 1] <= hours)
             || (p.x < columns - 1 && hourGrid[p.y][p.x + 1] <= hours)
             || (p.y > 0           && hourGrid[p.y - 1][p.x] <= hours)
             || (p.y < rows - 1    && hourGrid[p.y + 1][p.x] <= hours)) {
                // Node can receive from a neighbor, so will be able to send in 1 hour
                hourGrid[p.y][p.x] = hours + 1;
            } else {
                // Not receiving yet, so add to queue for next round
                notYet.add(p);
            }
        }
        pending = notYet;
    }
    return hours;
}

For testing, building a List<List<Integer>>, and sending in separate rows and columns values, is cumbersome, so here is a helper method:

static int hours(int[][] grid) {
    final int rows = grid.length;
    final int columns = grid[0].length;
    List<List<Integer>> gridList = new ArrayList<>(rows);
    for (int[] row : grid) {
        List<Integer> rowList = new ArrayList<>(columns);
        for (int value : row)
            rowList.add(value); // autoboxes
        gridList.add(rowList);
    }
    return hours(rows, columns, gridList);
}

Test

System.out.println(hours(new int[][] { // data from question
    { 0, 1, 1, 0, 1 },
    { 0, 1, 0, 1, 0 },
    { 0, 0, 0, 0, 1 },
    { 0, 1, 0, 0, 0 },
}));
System.out.println(hours(new int[][] { // data from answer
    { 0, 1, 1, 0, 1 },
    { 0, 1, 0, 0, 0 },
    { 0, 0, 0, 0, 1 },
    { 0, 0, 0, 1, 0 },
}));

Output

2
3

Answer 2

This seemed to work.

      List<List<Integer>> grid = 
            new ArrayList<>(List.of(
      new ArrayList<>(List.of(0, 1, 1, 0, 1)),
      new ArrayList<>(List.of( 0, 1, 0, 1, 0)),
      new ArrayList<>(List.of( 0, 0, 0, 0, 1)),
      new ArrayList<>(List.of( 0, 1, 0, 0, 0))));

      int total =0; 
      while (hours(4,4,grid) > 0) {
         total++;
      }

      System.out.println(total + " hours");

   }

   public static void display(List<List<?>> grid) {
      for (List<?> row : grid) {
         System.out.println(row);
      }
      System.out.println();
   }
   public static int hours(int rows, int cols, List<List<Integer>> grid) {
      int count = 0;

      // count the remaining 0's and change
      // the new guys to 1.
      for (int r = 0; r < rows; r++) {
         for (int c = 0; c < cols; c++) {
            if (grid.get(r).get(c) == 0) {
               count++;
            }
            if (grid.get(r).get(c) == -2) {
               grid.get(r).set(c, 1);
            }
         }
      }
      if (count == 0) {
         return 0;
      }
      for (int r = 0; r < rows; r++) {
         for (int c = 0; c < cols; c++) {

            if (grid.get(r).get(c) == 1 && grid.get(r).get(c) != -2) {
               if (r + 1 < rows) {
                  if (grid.get(r + 1).get(c) == 0) {
                     grid.get(r + 1).set(c, -2);
                  }
               }
               if (r - 1 >= 0) {
                  if (grid.get(r - 1).get(c) == 0) {
                     grid.get(r - 1).set(c, -2);
                  }
               }
               if (c + 1 < cols) {
                  if (grid.get(r).get(c + 1) == 0) {
                     grid.get(r).set(c + 1, -2);
                  }
               }
               if (c - 1 >= 0) {
                  if (grid.get(r).get(c - 1) == 0) {
                     grid.get(r).set(c - 1, -2);
                  }
               }
            }
         }
      }

      return count;
   }
}