Easy DP solution in C++ with detailed explanations (8ms, O(n^2) time and O(n) space)


  • 354

    Well, this problem desires for the use of dynamic programming. They key to any DP problem is to come up with the state equation. In this problem, we define the state to be the maximal size of the square that can be achieved at point (i, j), denoted as P[i][j]. Remember that we use size instead of square as the state (square = size^2).

    Now let's try to come up with the formula for P[i][j].

    First, it is obvious that for the topmost row (i = 0) and the leftmost column (j = 0), P[i][j] = matrix[i][j]. This is easily understood. Let's suppose that the topmost row of matrix is like [1, 0, 0, 1]. Then we can immediately know that the first and last point can be a square of size 1 while the two middle points cannot make any square, giving a size of 0. Thus, P = [1, 0, 0, 1], which is the same as matrix. The case is similar for the leftmost column. Till now, the boundary conditions of this DP problem are solved.

    Let's move to the more general case for P[i][j] in which i > 0 and j > 0. First of all, let's see another simple case in which matrix[i][j] = 0. It is obvious that P[i][j] = 0 too. Why? Well, since matrix[i][j] = 0, no square will contain matrix[i][j]. According to our definition of P[i][j], P[i][j] is also 0.

    Now we are almost done. The only unsolved case is matrix[i][j] = 1. Let's see an example.

    Suppose matrix = [[0, 1], [1, 1]], it is obvious that P[0][0] = 0, P[0][1] = P[1][0] = 1, what about P[1][1]? Well, to give a square of size larger than 1 in P[1][1], all of its three neighbors (left, up, left-up) should be non-zero, right? In this case, the left-up neighbor P[0][0] = 0, so P[1][1] can only be 1, which means that it contains the square of itself.

    Now you are near the solution. In fact, P[i][j] = min(P[i - 1][j], P[i][j - 1], P[i - 1][j - 1]) + 1 in this case.

    Taking all these together, we have the following state equations.

    1. P[0][j] = matrix[0][j] (topmost row);
    2. P[i][0] = matrix[i][0] (leftmost column);
    3. For i > 0 and j > 0: if matrix[i][j] = 0, P[i][j] = 0; if matrix[i][j] = 1, P[i][j] = min(P[i - 1][j], P[i][j - 1], P[i - 1][j - 1]) + 1.

    Putting them into codes, and maintain a variable maxsize to record the maximum size of the square we have seen, we have the following (unoptimized) solution.

    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (!m) return 0;
        int n = matrix[0].size();
        vector<vector<int> > size(m, vector<int>(n, 0));
        int maxsize = 0;
        for (int j = 0; j < n; j++) {
            size[0][j] = matrix[0][j] - '0';
            maxsize = max(maxsize, size[0][j]);
        }
        for (int i = 1; i < m; i++) {
            size[i][0] = matrix[i][0] - '0';
            maxsize = max(maxsize, size[i][0]);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    size[i][j] = min(size[i - 1][j - 1], min(size[i - 1][j], size[i][j - 1])) + 1;
                    maxsize = max(maxsize, size[i][j]);
                }
            }
        }
        return maxsize * maxsize;
    }
    

    Now let's try to optimize the above solution. As can be seen, each time when we update size[i][j], we only need size[i][j - 1], size[i - 1][j - 1] (at the previous left column) and size[i - 1][j] (at the current column). So we do not need to maintain the full m*n matrix. In fact, keeping two columns is enough. Now we have the following optimized solution.

    int maximalSquare(vector<vector<char>>& matrix) {
    	int m = matrix.size();
    	if (!m) return 0;
    	int n = matrix[0].size();
    	vector<int> pre(m, 0);
    	vector<int> cur(m, 0);
    	int maxsize = 0;
    	for (int i = 0; i < m; i++) {
    		pre[i] = matrix[i][0] - '0';
    		maxsize = max(maxsize, pre[i]);
    	}
    	for (int j = 1; j < n; j++) {
    		cur[0] = matrix[0][j] - '0';
    		maxsize = max(maxsize, cur[0]);
    		for (int i = 1; i < m; i++) {
    			if (matrix[i][j] == '1') {
    				cur[i] = min(cur[i - 1], min(pre[i - 1], pre[i])) + 1;
    				maxsize = max(maxsize, cur[i]);
    			}
    		}
    		swap(pre, cur);
    		fill(cur.begin(), cur.end(), 0);
    	}
    	return maxsize * maxsize;
    }
    

    Now you see the solution is finished? In fact, it can still be optimized! In fact, we need not maintain two vectors and one is enough. If you want to explore this idea, please refer to the answers provided by @stellari below. Moreover, in the code above, we distinguish between the 0-th row and other rows since the 0-th row has no row above it. In fact, we can make all the m rows the same by padding a 0 row on the top (in the following code, we pad a 0 on top of dp). Finally, we will have the following short code :) If you find it hard to understand, try to run it using your pen and paper and notice how it realizes what the two-vector solution does using only one vector.

    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> dp(m + 1, 0);
        int maxsize = 0, pre = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 1; i <= m; i++) {
                int temp = dp[i];
                if (matrix[i - 1][j] == '1') {
                    dp[i] = min(dp[i], min(dp[i - 1], pre)) + 1;
                    maxsize = max(maxsize, dp[i]);
                }
                else dp[i] = 0; 
                pre = temp;
            }
        }
        return maxsize * maxsize;
    }
    

    This solution, since posted, has been suggested various improvements by kind people. For a more comprehensive collection of the solutions, please visit my technical blog.


  • 26
    S

    Good O(n) memory solution. A minor optimization could be to use two pointers to pre and cur and only swap those pointers to avoid vector copying.

    Also, if you think about it, it is actually enough to use one vector only instead of two. The whole purpose of maintaining two arrays is that we want to keep the information of pre[i-1]. So we just need to use another variable to keep track of its value:

    class Solution {
    public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int nr = matrix.size(); if (nr == 0) return 0;
        int nc = matrix[0].size(); if (nc == 0) return 0;
        
        vector<int> dp(nc+1, 0);
        
        int maxsize = 0;
        
        int last_topleft = 0;  // This is 'pre[i-1]' for the current element
        
        for (int ir = 1; ir <= nr; ++ir) {
            for (int ic = 1; ic <= nc; ++ic) {
                int temp = dp[ic];      // This is 'pre[i-1]' for the next element                
                 if (matrix[ir-1][ic-1] == '0') dp[ic] = 0; 
                else {
                    dp[ic] = min(min(dp[ic], dp[ic-1]), last_topleft) + 1;
                    maxsize = max(maxsize, dp[ic]);
                }
                last_topleft = temp;  // update 'pre[i-1]'
            }
        }
        return maxsize * maxsize;
    }
    };

  • 3

    I think there is no need to use external matrix or vector. we can update the matrix itself.

    class Solution {
    public:
        int maximalSquare(std::vector<std::vector<char> > &matrix) {
            if(matrix.empty())
                return 0;
            int rows = matrix.size(), cols = matrix[0].size();
            char maxSize = '0';
            for (int j = 0; j < cols; ++j)
    			if (matrix[0][j] == '1') {
    				maxSize = '1';
    				break;
    			}
            for (int i = 1; i < rows; ++i) {
                maxSize = std::max(maxSize, matrix[i][0]);
                for (int j = 1; j < cols; ++j)
                    if (matrix[i][j] == '1') {
                        matrix[i][j] = std::min(matrix[i - 1][j - 1], std::min(matrix[i - 1][j], matrix[i][j - 1])) + 1;
                        maxSize = std::max(maxSize, matrix[i][j]);
                    }
            }
            return (maxSize - '0') * (maxSize - '0');
        }
    };

  • 1

    Hi, your solution is much more memory efficient. From the perspective of problem solving (less time and less memory), it is certainly more desirable. However, personally I would like to keep the input unchanged in functions with return values, which I guess is a good choice in practice :)


  • 0

    Wow, nice observations! I have updated the vector copy of my code to be swap(pre, cur);. Do you think it meets your idea? I also mention your one-vector solution in the post above. Thank you!


  • 0
    S

    Well, actually what I have in mind is to have two pointers to pre and cur as such: vector<int> *pp = &pre, *pc = &cur, and always use (*pp)[i] instead of pre[i]. When we need to swap two vectors, simply do swap(pp, pc). This way, there would be no data copying involved at all. swap(pre, cur) still does data copying behind the scene, so I think it is no better than your original implementation. However, I do agree that using the pointer method may slightly reduce readability. Maybe in a real interview, a good strategy is to write the code in your original way, but point it out to the interviewer that the swapping can actually be optimized as above.


  • 0

    Hi, stellari. I haven taken your idea and updated my code as follows.

    int maximalSquare(vector<vector<char>>& matrix) {
    	if (matrix.empty()) return 0;
    	int m = matrix.size(), n = matrix[0].size();
    	vector<int> pre(m, 0), cur(m, 0);
    	auto ppre = &pre, pcur = &cur;
    	int maxsize = 0;
    	for (int i = 0; i < m; i++) {
    		(*ppre)[i] = matrix[i][0] - '0';
    		maxsize = max(maxsize, pre[i]);
    	}
    	for (int j = 1; j < n; j++) {
    		(*pcur)[0] = matrix[0][j] - '0';
    		maxsize = max(maxsize, (*pcur)[0]);
    		for (int i = 1; i < m; i++) {
    			if (matrix[i][j] == '1') {
    				(*pcur)[i] = min((*pcur)[i - 1], min((*ppre)[i - 1], (*ppre)[i])) + 1;
    				maxsize = max(maxsize, (*pcur)[i]);
    			}
    		}
    		swap(ppre, pcur);
    		fill((*pcur).begin(), (*pcur).end(), 0);
    	}
    	return maxsize * maxsize;
    }
    

    I guess it is what you want? Thank you for your nice suggestions!


  • 2
    S

    As memory efficient as this solution is, I think it is generally best to avoid any direct modification on the original array. In most situations, updating the input matrix this way is an unexpected behavior, and may cause hard-to-catch bugs. Moreover, you may not even able to get the correct result due to data-type incompatibility. Here, the input is a 2d vector of CHAR, which typically holds values in the range of -128~127. So what if the side of the maximal square exceeds 127? The program would naturally fail, but since the basic logic of your program is correct, it may take a while for the tester to realize that this bug is actually caused by overflowing.

    Also, your interviewer may notice this problem earlier than you do and may use this to attack you, and it won't look good if you fail to discover the problem even after he brings it about.

    IMHO, we might as well avoid these problems since day 1 by not touching the original array.


  • 0

    Hi, stellari, thank you very much for your guidance!


  • 1

    swap(pre, cur) still does data copying behind the scene

    No it doesn't. See this and this.


  • 0
    Z

    top left can also be checked directly by comparing if it is ‘1’ in the matrix. Assume k = min(dp[ic], dp[ic-1]); Then dp[ic] = (matrix[ir-k-1][ic-k-1] == ‘1') ? k+1 : k;


  • 0
    S

    Good point! Thank you for this suggestion!


  • 0

    Thank you for your tips.


  • 0
    C

    nice work! Should pre set to 0 for i = 1? Otherwise, pre is the dp of the end of the previous line.


  • 0

    In the last solution, pre is set to 0 to include the case for the first row.


  • 0
    S

    excellent, thanks for sharing


  • 0
    Y

    i think you do not make the [i][j] = min(P[i - 1][j], P[i][j - 1], P[i - 1][j - 1]) + 1 sense or i'm too stupid to get it ....can you explain to me again?


  • 1
    O

    best explanation. thank you for your kind work


  • 0
    J
    This post is deleted!

  • 0
    X

    Awesome explanation. Can't wait to give you an UP!! Thanks for sharing!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.