How can I encompass a region of a 2D Array with a square based on the elements in the array?

user_13471744 0
Viewed 68

To provide a simple example, my problem is this:

I have a 2D array of 1s and 0s. Most of the grid is 0s, but there are some 1s scattered in there. I want to create a square that encompasses all of the 1's without any unnecessary space by finding the indexes of top-left and bottom-right elements of such a square.

I hope this helps visualize what I'm trying to do:

       0 1 2 3 4 5 6 7 8 9

   A   0 0 0 0 0_0_0_0_0 0
   B   0 0 0 0|0 0 1 0 0|0
   C   0 0 0 0|1 1 1 0 0|0
   D   0 0 0 0|0 0 0 1 1|0
   E   0 0 0 0|1 0 0 0 0|0
   F   0 0 0 0|0_1_0_0_0|0
   G   0 0 0 0 0 0 0 0 0 0
   H   0 0 0 0 0 0 0 0 0 0

So in this case, I would want to find the indexes of B4 and F8. I am working in Java and would like a solution that does not use Collections.

multidimensional-array arrays algorithm java
1 Answers

You have to iterate over the given array and track minimum and maximum indices (of both outer array and inner arrays) of the element with a value of 1.

In Java in need to initialize a local variable before you can access it. Therefore, all max variables are initiated with a value of -1 and max variables with a corresponding array length (invalid indices).

public static void main(String[] args) {
    int[][] grid = {
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 0},
            {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

    int minRow = grid.length;
    int minCol = grid[0].length;
    int maxRow = -1;
    int maxCol = -1;
    for (int row = 0; row < grid.length; row++) {
        for (int col = 0; col < grid[0].length; col++) {
            if (grid[row][col] == 0) continue; // skipping this element

            minRow = Math.min(row, minRow);
            minCol = Math.min(col, minCol);
            maxRow = Math.max(row, maxRow);
            maxCol = Math.max(col, maxCol);
        }
    }

    if (maxRow == -1) {
        System.out.println("The given array has no elements with value of 1");
    } else {
        System.out.println("minRow: " + minRow);
        System.out.println("minCol: " + minCol);
        System.out.println("maxRow: " + maxRow);
        System.out.println("maxCol: " + maxCol);
    }
}

Output

minRow: 1
minCol: 4
maxRow: 5
maxCol: 8

Sidenote: from the perspective of object-oriented design, this functionality can be encapsulated in a class, let's say MatrixStatistics. That will allow you to store these data, and might be something like element count, or histogram of frequencies for each subarray inside an object. Which can be returned from a method (as you know, it's not possible to return multiple values from the method), or used as a field. As an example from the JDK of such a mutable object caring statistical data, you might take a look at IntSummaryStatistics class.

user_179499450
Related