java – Find a "hole" in a two-dimensional array

Question:

Hello everyone, I faced one problem and find it difficult to write the code. Please help. Given: Two-dimensional array ->

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

Input: define that hole k is when all zeros in the row, and all 1s in the column except for k itself, which is 0. Output: does such k exist and if yes, return its value; if not, return -1. The code must go through with O (n) complexity. Method: public static int isSink (int [] [] mat)

I wrote this code, but I was told that it is incorrect:

public static int isSink(int[][] mat) {
    int n = mat[0].length;
    boolean[] check = new boolean[n];
    for (int i = 0; i < n; i++)
        check[i] = true;
    for (int i = 0; i < n; i++)
        if (check[i]) {
            for (int j = 0; j < n; j++) {
                if (i != j)
                    check[j] = false;
                else {
                    check[i] = false;
                    break;
                }
                if (i == j)
                    continue;
                if (mat[j][i] == 1)
                    check[j] = false;
                else {
                    check[i] = false;
                    break;
                }
            }
            if (check[i])
                return i;
        }
    return -1;
}

Answer:

This method works only for square matrices.

public static int isSink(int[][] mat) {
    int rowSum = 0;
    int colSum = 0;
    int colHeight = mat[0].length;

    int iterrationCounter = 0;

    int rowIndex = -1;
    int colIndex = -1;
    for (int i = 0; i < mat.length; i++) {
        for (int j = 0; j < mat[i].length; j++) {
            // Находи суммы элементов строки(rowSum) и столбца(colSum)
            rowSum += mat[i][j];
            colSum += mat[j][i];
            iterrationCounter++;
        }


        // Ищем строку в которой все элементы равны 0
        // т.е. сумма элементов, такой строки, равна 0
        if (rowIndex == -1 && rowSum == 0) {
            rowIndex = i;
        } else {
            rowSum = 0;
        }

        // Ищем столбец в котором все элементы, за исключением k, равны 1
        // т.е. сумма элементов, такого столбца, равна (высота столбца - 1)
        if (colIndex == -1 && colSum == colHeight - 1) {
            colIndex = i;
        } else {
            colSum = 0;
        }
    }

    System.err.println(iterrationCounter);

    if (rowIndex != -1 && colIndex != -1) {
        System.out.println("The sink is found by row:" + rowIndex + " column:" + colIndex);
        return mat[rowIndex][colIndex];
    }

    return -1;
}
Scroll to Top