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.

CodePudding user response：

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 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

CodePudding user response：

1. Have 4 variables: top, left, right, bottom
2. Start a simple traversal of the matrix.
3. top = index of row where first 1 occurs, bottom = index of row where last 1 occurs
4. left = index of column where first 1 occurs, right = index of column where last 1 occurs

Your required coordinates are (left, top) and (right, bottom). Really simple O(number of matrix elements) approach, really straightforward to implement