# 2 intuitive JAVA Solution. O(n) space

• Solution 1: this is a very simple way of thinking. If we want to know n, then we check 1 + (n - 1), 2 + (n - 2).....

``````public int numSquares(int n) {
// use dp idea
// m[i] represent the least number of perfect square numbers
// base case m[1] = 1;
// induction rule: if m[i] is square of some number, m[i] = 1;
// otherwise m[i] = min(m[1] + m[i - 1], m[2] + m[i - 2])
// use a hashset to store all square number
// space complexity is O(n)
// time complexity is O(n)
int[] m = new int[n + 1];
m[1] = 1;
Set<Integer> square = new HashSet<Integer>();
int i = 1;
while (i * i <= n) {
i++;
}
for (i = 2; i <= n; i++) {
if (square.contains(i)) {
m[i] = 1;
continue;
}
int min = Integer.MAX_VALUE;
for (int j = 1; j <= i / 2; j++) {
min = Math.min(min, m[j] + m[i - j]);
}
m[i] = min;
}
return m[n];
}
``````

Solution2: further thinking: we can check history more efficiency. We want to know n, then we check n - 1, n - 4, n - 9.....
So the time complexity will be O(sqrt(n)), instead of solution 1 O(n)

``````public int numSquares(int n) {
// use dp idea
// m[i] represent the least number of perfect square numbers
// base case m[1] = 1;
// induction rule: if m[i] is square of some number, m[i] = 1;
// otherwise m[i] = min(1 + m[i - 1], 4 + m[i - 4])
// use a hashset to store all square number
// space complexity is O(n)
// time complexity is O(n)

// sanity check
int[] m = new int[n + 1];
m[1] = 1;
Set<Integer> square = new HashSet<Integer>();
int i = 1;
while (i * i <= n) {
i++;
}
for (i = 2; i <= n; i++) {
if (square.contains(i)) {
m[i] = 1;
continue;
}
int min = Integer.MAX_VALUE;
for (int j = 1; j * j < i; j++) {
min = Math.min(min, m[i - j * j] + 1);
}
m[i] = min;
}
return m[n];
}
``````

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