The trick here is to name the state correctly, then let the implementation follow. For 279. Perfect Squares, the solution in this repository is mainly a graph traversal solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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: graph traversal, dynamic programming, bit manipulation.
The notes already sitting in the source point us in the right direction:
- TLE
- 545 / 588 test cases passed.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are numSquares, cntPerfectSquares.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The queue gives the solution a level-by-level or frontier-style traversal.
- 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:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//545 / 588 test cases passed.
03class Solution {
04public:
05 int numSquares(int n) {
06 //padding ahead
07 vector<int> dp(n+1, 0);
08
09 for(int i = 1; i*i <= n; ++i){
10 dp[i*i] = 1;
11 }
12
13 for(int i = 1; i <= n; ++i){
14 if(dp[i] == 0){
15 //cout << "i: " << i << endl;
16 int count = INT_MAX;
17 for(int j = 1; j <= i/2; ++j){
18 //cout << j << " and " << i-j << " : " << dp[j] << " and " << dp[i-j] << endl;
19 count = min(count, dp[j] + dp[i-j]);
20 }
21 dp[i] = count;
22 //cout << "i: " << i << ", dp[i]: " << dp[i] << endl;
23 }
24 }
25
26 return dp[n];
27 }
28};
29
30//DP
31//https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)
32//Runtime: 320 ms, faster than 29.50% of C++ online submissions for Perfect Squares.
33//Memory Usage: 9 MB, less than 69.72% of C++ online submissions for Perfect Squares.
34class Solution {
35public:
36 int numSquares(int n) {
37 //padding ahead
38 vector<int> dp(n+1, 0);
39
40 for(int i = 1; i <= n; ++i){
41 int count = INT_MAX;
42 /*
43 i = j*j + (i-j*j) for j <= sqrt(i)
44 */
45 for(int j = 1; j*j <= i; ++j){
46 count = min(count, dp[i-j*j]+1);
47 }
48 dp[i] = count;
49 }
50
51 return dp[n];
52 }
53};
54
55//static DP
56//https://leetcode.com/problems/perfect-squares/discuss/71512/Static-DP-C%2B%2B-12-ms-Python-172-ms-Ruby-384-ms
57//Runtime: 8 ms, faster than 95.54% of C++ online submissions for Perfect Squares.
58//Memory Usage: 6.2 MB, less than 84.31% of C++ online submissions for Perfect Squares.
59class Solution {
60public:
61 int numSquares(int n) {
62 //padding ahead
63 /*
64 https://leetcode.com/problems/perfect-squares/discuss/71512/Static-DP-C++-12-ms-Python-172-ms-Ruby-384-ms/173951
65 it's not magic by C++, but from leetcode, to save computing,
66 leetcode will not clear your initialization in each testcase.
67 that means, if you use static,
68 your previous caching will be used by later case.
69 you know, this is cheating.
70 and I don't recommend people to use leetcode specified code.
71 in the real interview, you won't have the cheating chance.
72 */
73 /*
74 note: if we create a fixed size vector,
75 it will generate heap-buffer-overflow,
76 because leetcode is reusing the vector,
77 so we need to dynamically change its size to fit different testcases
78 */
79 static vector<int> dp = {0};
80
81 while(dp.size() <= n){
82 int i = dp.size();
83 int count = INT_MAX;
84 /*
85 i = j*j + (i-j*j) for j <= sqrt(i)
86 */
87 // cout << "i: " << i << endl;
88 for(int j = 1; j*j <= i; ++j){
89 // cout << i-j*j << endl;
90 count = min(count, dp[i-j*j]+1);
91 }
92 dp.push_back(count);
93 }
94
95 // cout << "n: " << n << endl;
96 return dp[n];
97 }
98};
99
100//Math 1
101//https://leetcode.com/problems/perfect-squares/discuss/71533/O(sqrt(n))-in-Ruby-C%2B%2B-C
102//Runtime: 4 ms, faster than 98.45% of C++ online submissions for Perfect Squares.
103//Memory Usage: 5.9 MB, less than 96.71% of C++ online submissions for Perfect Squares.
104//time: O(sqrt(N)), space: O(1)
105class Solution {
106public:
107 int numSquares(int n) {
108 /*
109 if n = 4^a*(8b+7),
110 n is a sum of 4 squares
111 */
112 while(n % 4 == 0){
113 n /= 4;
114 }
115
116 if(n%8 == 7) return 4;
117
118 for(int a = 0; a*a <= n; ++a){
119 int b = sqrt(n-a*a);
120 if(a*a + b*b == n){
121 //!!a: (a != 0)
122 return 1 + !!a;
123 }
124 }
125
126 return 3;
127 }
128};
129
130//Math 2
131//https://leetcode.com/problems/perfect-squares/discuss/71533/O(sqrt(n))-in-Ruby-C%2B%2B-C
132//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Perfect Squares.
133//Memory Usage: 5.9 MB, less than 99.60% of C++ online submissions for Perfect Squares.
134//time: O(sqrt(N)), space: O(1)
135class Solution {
136public:
137 int numSquares(int n) {
138 /*
139 if n = 4^a*(8b+7),
140 n is a sum of 4 squares
141 */
142 while(n % 4 == 0){
143 n /= 4;
144 }
145
146 if(n%8 == 7) return 4;
147
148 bool min2 = false;
149
150 for(int factor = 2; factor <= n; ++factor){
151 //?
152 if(factor > n/factor){
153 factor = n;
154 }
155
156 int exp = 0;
157 while(n % factor == 0){
158 n /= factor;
159 ++exp;
160 }
161
162 //one of the factors is 3 modulo 4
163 if(factor%4 == 3 && exp%2 == 1){
164 return 3;
165 }
166
167 /*
168 if there is a factor whose exp is odd,
169 then min2 will be 1
170 */
171 min2 |= exp%2;
172 }
173
174 /*
175 if every factor's power is even,
176 then return 1, o.w. return 2
177 */
178 return 1 + min2;
179 }
180};
181
182//BFS
183//https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)
184//Runtime: 32 ms, faster than 91.85% of C++ online submissions for Perfect Squares.
185//Memory Usage: 11 MB, less than 21.42% of C++ online submissions for Perfect Squares.
186class Solution {
187public:
188 int numSquares(int n) {
189 if(n <= 0) return 0;
190
191 vector<int> perfectSquares;
192 //padding ahead
193 vector<int> cntPerfectSquares(n+1);
194
195 for(int i = 0; i*i <= n; ++i){
196 perfectSquares.push_back(i*i);
197 cntPerfectSquares[i*i] = 1;
198 }
199
200 if(perfectSquares.back() == n){
201 return 1;
202 }
203
204 queue<int> q;
205 for(int& e : perfectSquares){
206 q.push(e);
207 }
208
209 //also, the level of the tree
210 int currCntPerfectSquares = 1;
211 //bfs
212 while(!q.empty()){
213 ++currCntPerfectSquares;
214 int levelSize = q.size();
215
216 while(levelSize-- > 0){
217 int node = q.front(); q.pop();
218
219 for(auto& ps : perfectSquares){
220 if(node + ps == n){
221 return currCntPerfectSquares;
222 }else if(node+ps <= n && cntPerfectSquares[node+ps] == 0){
223 //node+ps is what we focus and not visited yet
224 cntPerfectSquares[node+ps] = currCntPerfectSquares;
225 q.push(node+ps);
226 }else if(node+ps > n){
227 //only focus on numbers <= n
228 break;
229 }
230 }
231 }
232 }
233
234 return 0;
235 }
236};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.