# Time limit exceeded in K-th symbol in Grammar (LeetCode)

I am taking efforts to solve problem K-th Symbol in Grammar - LeetCode

1. K-th Symbol in Grammar

On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

Examples:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

Explanation:
row 1: 0
row 2: 01
row 3: 0110
row 4: 01101001


Note:

1. N will be an integer in the range [1, 30].
2. K will be an integer in the range [1, 2^(N-1)].

My solution

class Solution:
def kthGrammar(self, N: int, K: int) -> int:
#replace function
def replace(row: "List[int]") -> "List[int]":
"""
rtype: row
"""
for i in range(len(row)):
print(row[i])
if row[i] == 0: #0 -> 01
row.insert(2*i+1, 1)
elif row[i] == 1: #1 -> 10
row.insert(2*i+1, 0)
return row

#helper function
def helper(N: int) -> "List(int)":
"""
rtype:the last row
"""
#error case
if N < 1: return []
#base case
if N == 1:
res = [0]
return res
elif N > 1:
return replace(helper(N-1))

#error cases
if N < 1 or K < 1 or K > 2**(N-1) : return None
#recur
row = helper(N)
#logging.debug(f"row: {row}")
return row[K-1]


Unfortunately it reported Time Limit Exceeded

Last executed input: 30 434991989

Review my solution:

1. employed tail recursion return replace(helper(N-1))
2. did not create a new row

It's a relatively fine solution,

What might be the reason of TLE?