K-th Symbol in Grammar: Recursive Binary Pattern

You are building a table of n rows. Row 1 starts as "0". For every subsequent row, you take the previous row and replace each "0" with "01" and each "1" with "10". Given two integers n and k, return the k-th symbol (1-indexed) in the n-th row.

This is LeetCode 779: K-th Symbol in Grammar. At first glance, it looks like you need to build the entire row and index into it. But row n has 2^(n-1) characters, which means row 30 alone has over 500 million characters. You cannot build the row directly. Instead, you need to recognize the recursive structure hiding inside the generation rules.

Why this problem matters

This problem is a clean test of recursive thinking. There is no data structure to set up, no edge-case-heavy parsing, and no tricky math formula. The entire solution comes down to one observation: every symbol in row n is determined by a single symbol in row n-1. Once you see that, the code writes itself.

The pattern here connects to a broader category of problems where the answer at position k depends on the answer at a smaller position. You will see this same "trace back to the parent" idea in problems involving binary trees, divide and conquer, and bit manipulation. Getting comfortable with this kind of recursive reduction is a skill that transfers directly to harder problems.

It also teaches you to resist the urge to simulate. When the problem says "build a table," your first instinct might be to literally build it. Learning to ask "do I actually need to construct this?" is one of the most valuable habits you can develop for interviews.

The key insight

Look at how each row is generated. A 0 in row n-1 becomes 01 in row n. A 1 in row n-1 becomes 10 in row n. This means position k in row n has a parent in row n-1.

The parent lives at position ceil(k / 2), which you can compute as (k + 1) // 2. Now the question is: does the child match the parent, or is it flipped?

• If k is odd, the child is the left output of the parent. For both rules (0->01 and 1->10), the left output matches the parent. So the child equals the parent.
• If k is even, the child is the right output of the parent. For both rules, the right output is the opposite of the parent. So the child is 1 - parent.

That gives you a clean recursion that bottoms out at row 1, where the only symbol is 0.

def kth_grammar(n, k):
    if n == 1:
        return 0
    parent = kth_grammar(n - 1, (k + 1) // 2)
    if k % 2 == 1:
        return parent
    else:
        return 1 - parent

Each recursive call moves up one row and halves the position. You make exactly n - 1 calls before hitting the base case. No arrays, no string building, just a simple walk up the tree.

Step-by-step walkthrough

Let's trace through a concrete example: kth_grammar(n=4, k=5).

Row 4 is 01101001. The 5th character is 1. Here is how the recursion finds that answer without building the row.

The recursion drills down from row 4 to row 1, then unwinds. At row 1 the answer is 0. Coming back up, step 3 flips it to 1 (because k=2 is even). Steps 2 and 1 keep it unchanged (because k=3 and k=5 are both odd). The final answer is 1.

Notice how each level does almost no work. You check if k is odd or even, compute the parent position, and recurse. The entire trace fits on a napkin.

Complexity analysis

You could also convert this to an iterative solution by walking from row n down to row 1 in a loop, tracking whether you need to flip. That would reduce space to O(1), but the time stays O(n). Since n is at most 30 in the problem constraints, either version is more than fast enough.

Edge cases to watch for

• n = 1: the only symbol is 0. Return 0 immediately.
• k = 1 at any row: the first symbol of every row is always 0. Your recursion handles this naturally, since k=1 is always odd and traces back to k=1 in the previous row.
• Last element: when k = 2^(n-1), you are at the rightmost position. The recursion still works the same way, just with more even-position flips along the path.
• Large n: row 30 has over 500 million characters. Do not try to build the string. The recursive approach handles n=30 with just 29 function calls.

The building blocks

This problem is built on a few reusable ideas.

Recursion with size reduction. Each call reduces the problem from row n to row n-1 and from position k to roughly k/2. This "halving" structure is the same shape you see in binary search and divide-and-conquer algorithms.

Binary tree parent-child mapping. The relationship between position k in row n and position ceil(k/2) in row n-1 is exactly the parent formula in a 1-indexed binary tree. If you are comfortable navigating binary trees by index, this problem feels natural.

Complement/flip logic. The idea that a child is either the same as or the opposite of its parent shows up in problems involving XOR, Gray codes, and other binary sequence constructions. Recognizing when "flip or keep" is the core operation saves you from overcomplicating the logic.

From understanding to recall

You have traced through the recursion and the logic makes sense. But reading a solution and reproducing it under time pressure are different skills. In an interview, you need to identify the parent-child relationship, write the odd/even logic, and handle the base case, all without notes.

Spaced repetition locks this in. The first time you revisit this problem, you might need a minute to recall the parent formula. By the third repetition, the pattern is automatic: "each position traces to its parent at (k+1)//2, odd keeps, even flips." That kind of instant recall is what turns a 20-minute struggle into a 5-minute solve.

Related posts

• Fibonacci Number - Another recursive math pattern
• Power of Two - Binary number properties
• Counting Bits - Another problem with binary patterns