Given a sequence of number: 1, 11, 21, 1211, 111221, … The rule of generating the number in the sequence is as follow: 1 is "one 1" so 11. 11 is "two 1s" so 21. 21 is "one 2 followed by one 1" so 1211. Find the nth number in this sequence. Assumptions: n starts from 1, the first number is "1", the second number is "11"
My Solution:
public String countAndSay(int n) {
List<Integer> result = helper(n);
StringBuilder sb = new StringBuilder();
for(Integer num : result) {
sb.append(num);
}
return sb.toString();
}
private List<Integer> helper(int n) {
List<Integer> result = new ArrayList<Integer>();
//base case
if (n == 1) {
result.add(1);
return result;
}
List<Integer> smaller = helper(n - 1);
int count = 1;
for (int i = 0; i < smaller.size(); i++) {
if (i + 1 > smaller.size() - 1 ||
!smaller.get(i + 1).equals(smaller.get(i))) {
result.add(count);
result.add(smaller.get(i));
count = 1;
} else {
count++;
}
}
return result;
}
My understanding for the big O notation space complexity is that while the method is running, the max possible extra space which not waiting for garbage collection. So my thought on the space complexity of this solution is since the recursion call is done by the line "List smaller = helper(n - 1);", the extra space for the lower level of recursion call is already waiting for garbage collection. So that the time complexity of low level shouldn' t be counted into the current level. The space complexity of this solution should be O(n). Am I right?
Yes, in java perspective, you're right. Big O notations denotes the order of growth of the space/time with the increase of input size. The amount of space your code takes will linearly increase with the increase of input of n. So the space complexity of this solution is indeed O(n).
For recursion, the space complexity involves with the space taken in recursion/function stack at the worst case. Because the function calls which are currently in recursion stack are not qualified to current garbage collection call. The maximum space this program will take when the helper(1) will get called because at this moment helper(n), helper(n - 1) .... helper(2) all this calls with local resources are in recursion stack and are not qualified for garbage collection.
However, you can do it in constant space without the recursion.
public String countAndSay(int n) {
StringBuilder curr = new StringBuilder("1");
StringBuilder prev;
int count;
char say;
for (int i = 1; i < n; i++) {
prev = curr;
curr = new StringBuilder();
count = 1;
say = prev.charAt(0);
for (int j = 1, len = prev.length(); j < len; j++) {
if (prev.charAt(j) != say){
curr.append(count).append(say);
count = 1;
say = prev.charAt(j);
}
else count++;
}
curr.append(count).append(say);
}
return curr.toString();
}
Hope it helps!
I still have some confusion about the detail. When we called help(1), all help(2) to help(n) is in recursion stack, yet at that time, the space complexity for each stack is O(1) since we only created an empty List, and the maximum space complexity would be (n-1) * O(1) + O(n)(this is the list of helper(1)) = O(n).What I want to make sure is wheater this analysis is correct.
No, here is the picture of recursion stack. You can set breakpoint and debug to see what really happens.
call result size(when entered) result size(when function returns)
helper(n) 0 x(n)
helper(n - 1) 0 x(n - 1)
helper(n - 2) 0 x(n - 2)
.......
......
helper(3) 0 x2
helper(2) 0 x1
helper(1) 0 1
Here x(i) is the resultant size after executing this block:
int count = 1;
for (int i = 0; i < smaller.size(); i++) {
if (i + 1 > smaller.size() - 1 ||
!smaller.get(i + 1).equals(smaller.get(i))) {
result.add(count);
result.add(smaller.get(i));
count = 1;
} else {
count++;
}
}
You can use pen-and-paper or debug to see what's really happening under the recursion hood.