LeetCode 1504. Count Submatrices With All Ones in Java

In this post we will solve LeetCode 1504. Count Submatrices With All Ones problem using the Java programming language, the VSCode IDE on a Windows computer. My suggestion to you is that unless you have some special set of requirements, use the online IDE provided by LeetCode.

Given an m x n binary matrix mat, 
eturn the number of submatrices that have all ones.

Constraints:

o 1 <= m, n <= 150
o mat[i][j] is either 0 or 1.

Related Topics:

o Array
* Dynamic Programming
o Stack
o Matrix
o Monotonic Stack

In this problem we are provided a two dimensional matrix that only contains 1s and 0s. The dimensions are specified by `n` and `m`. Our mission if we wish to accept it, is to return the number of submatrices of 1s.

Like in most (never say all) problems, there are several approaches one can use to generate a solution. Some are better than others. That said, this problem seems to call for using dynamic programming to solve it. We should be able to somehow count the number of 1s and then figure out the combinations of `x` numbers taken `y` at a time. In my humble opinion this takes a lot of thinking and in some cases some luck.

    public int numSubmat(int[][] mat) {
        
    }

The signature for the function of interest is very simple and fits the requirements at hand.

3,3
1,0,1
1,1,0
main <<<  mat:
[1, 0, 1]
[1, 1, 0]
[1, 1, 0]
<<< dp:
[1, 0, 1]
[1, 2, 0]
[1, 2, 0]
<<< score: 1 (0,0)
<<< score: 1 (1,0)
<<< score: 1 (2,0)
<<< score: 1 (0,2)
<<< score: 0 (1,2)
<<< score: 0 (2,2)
<<< score: 1 (1,0)
<<< score: 1 (2,0)
<<< score: 2 (1,1)
<<< score: 2 (2,1)
<<< score: 1 (2,0)
<<< score: 2 (2,1)
main <<< numSubmat0: 13
<<<  mat:
[1, 0, 1]
[2, 1, 0]
[2, 1, 0]
<<< score: 1 (0,0)
<<< score: 1 (0,0)
<<< score: 1 (1,0)
<<< score: 1 (2,0)
<<< score: 1 (0,2)
<<< score: 1 (0,2)
<<< score: 2 (1,0)
<<< score: 2 (1,0)
<<< score: 2 (2,0)
<<< score: 1 (1,1)
<<< score: 1 (1,1)
<<< score: 1 (2,1)
<<< score: 2 (2,0)
<<< score: 2 (2,0)
<<< score: 1 (2,1)
<<< score: 1 (2,1)
main <<<  numSubmat: 13


3,4
0,1,1,0
0,1,1,1
1,1,1,0
main <<< rows: 3
main <<< cols: 4
main <<<  mat: 
[0, 1, 1, 0]
[0, 1, 1, 1]
[1, 1, 1, 0]
<<< dp: 
[0, 1, 2, 0]
[0, 1, 2, 3]
[1, 2, 3, 0]
<<< score: 1 (0,1)
<<< score: 1 (1,1)
<<< score: 1 (2,1)
<<< score: 2 (0,2)
<<< score: 2 (1,2)
<<< score: 2 (2,2)
<<< score: 1 (1,1)
<<< score: 1 (2,1)
<<< score: 2 (1,2)
<<< score: 2 (2,2)
<<< score: 3 (1,3)
<<< score: 0 (2,3)
<<< score: 1 (2,0)
<<< score: 2 (2,1)
<<< score: 3 (2,2)
main <<< numSubmat0: 24
<<<  mat:
[0, 2, 1, 0]
[0, 3, 2, 1]
[3, 2, 1, 0]
<<< score: 2 (0,1)
<<< score: 2 (0,1)
<<< score: 2 (1,1)
<<< score: 2 (2,1)
<<< score: 1 (0,2)
<<< score: 1 (0,2)
<<< score: 1 (1,2)
<<< score: 1 (2,2)
<<< score: 3 (1,1)
<<< score: 3 (1,1)
<<< score: 2 (2,1)
<<< score: 2 (1,2)
<<< score: 2 (1,2)
<<< score: 1 (2,2)
<<< score: 1 (1,3)
<<< score: 1 (1,3)
<<< score: 3 (2,0)
<<< score: 3 (2,0)
<<< score: 2 (2,1)
<<< score: 2 (2,1)
<<< score: 1 (2,2)
<<< score: 1 (2,2)
main <<<  numSubmat: 24

We will be generating two versions of the function of interest.

Each test case is separated from others by two blank lines. The test cases are the ones provided by LeetCode.

In a test case, the first line provides the dimensions of the matrix. The following `n` lines provide the values for each row in the matrix. The values are 1s or 0s.

Our test scaffold, which IS NOT PART OF THE SOLUTION, seems to read the input lines and populate the int[][] `mat`, the contents of the matrix are then displayed in order to make sure all is well before calling the function of interest. The function of interest is then called and the result displayed.

Please note that there are several lines displayed by the function of interest. Such lines ARE NOT PART OF THE SOLUTION. They are there to debug the code and help us understand what is going on.

https://math.stackexchange.com/questions/1117236/calculate-the-total-number-of-combinations-over-n-elements-where-the-number-of
Calculate the total number of combinations over n elements, 
where the number of elements in each subset is in {0,..,n}?

As usual I do some reading, you can call it research or refreshing, while thinking about the approach. Typically in an interview it is not possible to perform such a task, but in the real world that is how many developers (myself included) work.

    /**
     * Test scaffold
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read r and c ****
        int[] rc = Arrays.stream(br.readLine().trim().split(","))
                            .mapToInt(Integer::parseInt)
                            .toArray();

        // **** for ease of use ****
        int rows = rc[0];
        int cols = rc[1];

        // **** create matrix ****
        int[][] mat = new int[rows][];

        // **** populate matrix ****
        for (int r = 0; r < rows; r++)
            mat[r] = Arrays.stream(br.readLine().trim().split(","))
                            .mapToInt(Integer::parseInt)
                            .toArray();

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< rows: " + rows);
        System.out.println("main <<< cols: " + cols);
        System.out.println("main <<<  mat: ");
        for (int r = 0; r < rows; r++)
            System.out.println(Arrays.toString(mat[r]));

        // **** call function of interest and display result ****
        System.out.println("main <<< numSubmat0: " + numSubmat0(mat));


        // // ???? ????
        // System.out.println("main <<<  mat: ");
        // for (int r = 0; r < rows; r++)
        //     System.out.println(Arrays.toString(mat[r]));


        // **** call function of interest and display result ****
        System.out.println("main <<<  numSubmat: " + numSubmat(mat));


        // // ???? ????
        // System.out.println("main <<<  mat: ");
        // for (int r = 0; r < rows; r++)
        //     System.out.println(Arrays.toString(mat[r]));
    }

This is the test scaffold that was mentioned earlier. Please note that it IS NOT PART OF THE SOLUTION. The code reads the input lines, populates the int[][] `mat` matrix, calls two implementations of the function of interest and displays the associated results.

Please note that the contents of the `mat` matrix are displayed after the matrix is populated and after each invocation of the function of interest. As we will see shortly, one of the implementations modifies the input `mat` matrix. In production it is not a good thing to alter arguments. If needed one can create a copy and alter the copy to leave the argument untouched. You never know other functions / methods down the line might need the original matrix.

    /**
     * Given an m x n binary matrix mat, 
     * return the number of submatrices that have all ones.
     * 
     * Dynamic programming (with dp int[][] array).
     * 
     * Runtime: 8 ms, faster than 85.23% of Java online submissions.
     * Memory Usage: 42.8 MB, less than 43.11% of Java online submissions.
     * 
     * 73 / 73 test cases passed.
     * Status: Accepted
     * Runtime: 8 ms
     * Memory Usage: 42.8 MB
     */
    static public int numSubmat0(int[][] mat) {

        // **** initialization ****
        var num     = 0;
        var rows    = mat.length;
        var cols    = mat[0].length;
        int[][] dp  = new int[rows][cols];
        var score   = 0;

        // **** traverse rows in int[][] mat - 0(n) ****
        for (var r = 0; r < rows; r++) {

            // **** initialize score for this row ****
            score = 0;
            
            // **** traverse columns in this row - O(m) ****
            for (var c = 0; c < cols; c++) {

                // **** update score ****
                if (mat[r] == 1) score++;
                else score = 0;

                // **** place score in dp ****
                dp[r] = score;
            }
        }

        // ???? ????
        System.out.println("<<< dp: ");
        for (var r = 0; r < rows; r++)
            System.out.println(Arrays.toString(dp[r]));

        // **** rows ****
        for (var r = 0; r < rows; r++) {

            // **** columns ****
            for (var c = 0; c < cols; c++) {

                // **** skip this column ****
                if (dp[r] == 0) continue;

                // **** initialize score ****
                score = dp[r];
            
                // ???? ????
                System.out.println("<<< score: " + score + " (" + r + "," + c + ")");

                // **** update number ****
                num += score;

                // **** repeat rows ****
                for (var d = r + 1; d < rows; d++) {

                    // **** update score ****
                    score = Math.min(score, dp[d]);

                    // ???? ????
                    System.out.println("<<< score: " + score + " (" + d + "," + c + ")");

                    // **** update number ****
                    num += score;
                }
            }
        }

        // **** return number of submatrices ****
        return num;
    }

In this implementation we create an int[][] array named `dp`. We will use it to hold information that when properly used, should help us come up with the required solution.

The first loop is used to traverse the matrix one row at a time. This loop populates the `dp` int[][] matrix with counts of the number of 1s. We will need them to calculate combinations. In my opinion that was the easy part.

Now we need to traverse the `dp` matrix one column at a time, calculating the number of combinations. This took some reading about combinations, experimenting and optimizing.

The purpose of the second set of loops is to compute the number of combinations (`scores`) by traversing the columns multiple times moving the starting point one cell per pass.

The inner loop illustrates how the `score` is computed on each pass. The `num` variable is updated using the computed `score`.

When all is said and done, the contents of the `num` variable is returned.

Please take a look at the comments section of this function for performance information.

As we can tell after going over the code, this implementation uses and modifies the `dp` int[][] matrix. It does not modify the input `mat` int[][] matrix.

    /**
     * Given an m x n binary matrix mat, 
     * return the number of submatrices that have all ones.
     * 
     * Dynamic programming (no dp int[][] array).
     * 
     * Runtime: 9 ms, faster than 82.04% of Java online submissions.
     * Memory Usage: 53.2 MB, less than 14.37% of Java online submissions.
     * 
     * 73 / 73 test cases passed.
     * Status: Accepted
     * Runtime: 9 ms
     * Memory Usage: 53.2 MB
     */
    static public int numSubmat(int[][] mat) {

        // **** initialization ****
        var rows    = mat.length;
        var cols    = mat[0].length;
        var num     = 0;

        // **** traverse rows (top to bottom) ****
        for (int r = 0; r < rows; r++) {

            // **** traverse columns (right to left) ****
            for (int c = cols - 2; c >= 0; c--) {
                if (mat[r] == 1)
                    mat[r] += mat[r];
            }
        }
    
        // ???? ????
        System.out.println("<<<  mat:");
        for (int r = 0; r < rows; r++)
            System.out.println(Arrays.toString(mat[r]));

        // **** traverse rows (top to bottom) ****
        for (int r = 0; r < rows; r++) {

            // **** traverse columns (left to right) ****
            for (int c = 0; c < cols; c++) {

                // **** skip this column ****
                if (mat[r] == 0) continue;

                // **** initialize score ****
                var score = mat[r];

                // ???? ????
                System.out.println("<<< score: " + score + " (" + r + "," + c + ")");

                // **** traverse rows (top to bottom) ****
                for (int d = r; d < rows; d++) {

                    // **** skip this cell ****
                    if (mat[d] == 0) break;

                    // **** update score ****
                    score = Math.min(score, mat[d]);

                    // ???? ????
                    System.out.println("<<< score: " + score + " (" + d + "," + c + ")");

                    // **** update number ****
                    num += score;
                }
            }
        }

        // **** return number of submatrices ****
        return num;
    }

This is the second implementation of the function of interest.

This implementation is very similar to the previous one. The main difference is that it does not make use of a `dp` int[][] matrix by making changes directly into the int[][] `mat` array. In general this is not a good idea when working on production projects.

I am not going to go though the code due to the similarities with the previous implementation.

Please take a look at the comments section of this function. The function is slightly slower (1 ms) than the previous implementation. It seems that performance reports are affected by the number of simultaneous submissions at the LeetCode website. One way or the other, this implementation uses less space O(1) than the previous O(n * m).

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named CountSubmatricesWithAllOnes.

Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.

Thanks for reading, feel free to connect with me John Canessa at LinkedIn.

Enjoy;

John

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.