# Use Queue to save space

• Most of solutions straight use an array of size n to store the string, actually we can remove the used char, which makes queue an ideal data structure to save space:

``````class Solution {
public:
int magicalString(int n) {
if(n==0)
return 0;
if(n<=3)
return 1;
queue<char> Q;
int count=3,count1=1;
Q.push('2');
char p,q;
while(count<n){
p=Q.back();
q=Q.front();
Q.pop();
if(p=='1')
p='2';
else
p='1';
for(int k=q-'0';k>0;k--){
count++;
if(p=='1')
count1++;
if(count>=n)
return count1;
Q.push(p);
}
}
return count1;
}
};
``````

• I also used queue to "save space" but potentially you can push too much data in your queue, so it will be O(n) anyway. Or at least a big number so O(n) is a good assumption.

E.g. for n = 99999, my queue has 33347 elements in it. Hence no benefit. I've tried to check if the queue.size() + count are > n, then don't put anything into the queue, since it won't get popped anyway, but I didn't get any noticeable improvements in the running time of the algorithm :(

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