Problem statement

https://leetcode.com/problems/magical-string/

Solution

Actually, this is two pointers problem, where you generate our next data, using previous data. We keep two pointers: slow and fast, where slow is always behind (or equal at the beginning) of fast pointer. We add to the end 1 or 2 numbers, move our fast and slow iterators and change current number.

Complexity

Complexity, both time and space is O(n).

Code

class Solution:
    def magicalString(self, n):
        seq = [1,2,2]
        slow, fast, current = 2, 2, 1
        while fast <= n - 2:
            seq  += [current] * seq[slow]
            fast +=  seq[slow]
            current = 3 - current    
            slow += 1
        return 2*n - sum(seq[:n])