LeetCode: 779. K-th Symbol in Grammar

LeetCode: 779. K-th Symbol in Grammar

Summary

Return the k-th symbol in the n-th row of a table of n rows.

Rules:

• The 1st row starts with 0.
• From the 2nd row onward, replace each 0 with 01 and each 1 with 10 from the previous row.

Example:

n=1, k=1

row1: 0

n=2, k=1

row1: 0 row2: 01 -> 0

Approach

Recursive.

We can think of these rules as a binary tree.

From the (n, k) position, we move back toward the top and recursively check the parent value.

Function

• Parent index: (k + 1) // 2

• If the current row is n == 1, return 0.

• Otherwise, recursively find the previous node.

• If (prev is 0 and k is right) or (prev is 1 and k is left), return 1.

• Otherwise, return 0.

Complexity

Time Complexity: O(n) because we move from row n to row 1 once. Space Complexity: O(n) for the recursive call stack.