K-th Symbol in Grammar - Video Solutions

Problem Overview: You start with row 1 containing 0. Each next row replaces every 0 with 01 and every 1 with 10. Given n and k, return the k-th symbol in row n without constructing the entire row.

Approach 1: Recursive Parent Tracking (Time: O(n), Space: O(n))

The key observation: every element in row n is derived from a parent in row n-1. The first half of a row copies the parent value, while the second half flips it. Recursively determine the parent position (k+1)/2 in the previous row. If k is odd, the value is the same as the parent. If k is even, it is the flipped value (0→1, 1→0). This approach walks up the recursion tree until reaching the base case n = 1. Each recursive call moves one row upward, so the time complexity is O(n) and recursion stack space is also O(n). This method directly models the grammar definition and is easy to reason about during interviews.

Approach 2: Iterative Parity / Bit Insight (Time: O(n), Space: O(1))

The recursion can be converted into an iterative process by repeatedly moving from position k to its parent while tracking whether a flip occurs. When k is even, the symbol flips relative to its parent; when k is odd, it stays the same. Iterate while reducing k to (k+1)/2 and count how many flips happen. The final value equals the base symbol 0 XOR the number of flips modulo 2. This eliminates recursion and uses constant memory. The approach also connects to bit manipulation, since the answer effectively depends on the parity of transformations applied along the path to the root.

Recommended for interviews: The recursive approach is usually the first solution interviewers expect because it clearly follows the grammar definition and demonstrates understanding of the parent-child relationship between rows. After that, presenting the iterative version shows optimization awareness and familiarity with recursion elimination and mathematical parity reasoning.