This problem looks busy at first, but the accepted solution is built around one steady invariant. For 221. Maximal Square, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming.
The notes already sitting in the source point us in the right direction:
- Approach #1 Brute Force [Accepted]
- time: O((mn)^2), space: O(1)
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are maximalSquare.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(mn), space: O(mn)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//Approach #1 Brute Force [Accepted]
02//Runtime: 24 ms, faster than 33.17% of C++ online submissions for Maximal Square.
03//Memory Usage: 8.2 MB, less than 100.00% of C++ online submissions for Maximal Square.
04//time: O((mn)^2), space: O(1)
05class Solution {
06public:
07 int maximalSquare(vector<vector<char>>& matrix) {
08 int m = matrix.size();
09 if(m == 0) return 0;
10 int n = matrix[0].size();
11
12 int maxslen = 0;
13
14 for(int i = 0; i < m; i++){
15 for(int j = 0; j < n; j++){
16 if(matrix[i][j] == '0') continue;
17 int slen = 1;
18 bool valid = true;
19 while(slen + i < m && slen + j < n && valid){
20 for(int k = j; k <= j + slen; k++){
21 //i+slen: examine the (possible) last row of the square
22 if(matrix[i+slen][k] != '1'){
23 valid = false;
24 break;
25 }
26 }
27 for(int k = i; k <= i + slen; k++){
28 //j+slen: examine the (possible) last col of the square
29 if(matrix[k][j+slen] != '1'){
30 valid = false;
31 break;
32 }
33 }
34 if(valid){
35 slen++;
36 }
37 }
38 maxslen = max(maxslen, slen);
39 }
40 }
41
42 return maxslen * maxslen;
43 }
44};
45
46//Approach #2 (Dynamic Programming) [Accepted]
47//Runtime: 24 ms, faster than 33.17% of C++ online submissions for Maximal Square.
48//Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Maximal Square.
49//time: O(mn), space: O(mn)
50class Solution {
51public:
52 int maximalSquare(vector<vector<char>>& matrix) {
53 int m = matrix.size();
54 if(m == 0) return 0;
55 int n = matrix[0].size();
56
57 int maxslen = 0;
58 vector<vector<int>> dp(m+1, vector(n+1, 0));
59
60 for(int i = 1; i <= m; i++){
61 for(int j = 1; j <= n; j++){
62 if(matrix[i-1][j-1] == '0') continue;
63 //check top, left and top-left
64 dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
65 maxslen = max(maxslen, dp[i][j]);
66 }
67 }
68
69 return maxslen * maxslen;
70 }
71};
72
73//DP, O(n) space
74//Runtime: 20 ms, faster than 77.64% of C++ online submissions for Maximal Square.
75//Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Maximal Square.
76//time: O(mn), space: O(n)
77class Solution {
78public:
79 int maximalSquare(vector<vector<char>>& matrix) {
80 int m = matrix.size();
81 if(m == 0) return 0;
82 int n = matrix[0].size();
83
84 int maxslen = 0;
85 vector<int> dp(n+1, 0);
86
87 int prev = 0; //top-left
88
89 for(int i = 1; i <= m; i++){
90 for(int j = 1; j <= n; j++){
91 /*
92 dp[j] of previous row
93 it will be used as 'prev' in next j,
94 at that time, it means the dp value of top-left corner
95 */
96 int tmp = dp[j];
97 if(matrix[i-1][j-1] == '0'){
98 dp[j] = 0;
99 }else{
100 //check top, left and top-left
101 dp[j] = min({dp[j], dp[j-1], prev}) + 1;
102 maxslen = max(maxslen, dp[j]);
103 }
104
105 prev = tmp;
106 }
107 }
108
109 return maxslen * maxslen;
110 }
111};Cost