We build a table of n rows (1-indexed). We start by writing 0 in the 1st row. 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.
n = 3, the 1st row is 0, the 2nd row is 01, and the 3rd row is 0110.Given two integer n and k, return the kth (1-indexed) symbol in the nth row of a table of n rows.
Example 1:
Input: n = 1, k = 1 Output: 0 Explanation: row 1: 0
Example 2:
Input: n = 2, k = 1 Output: 0 Explanation: row 1: 0 row 2: 01
Example 3:
Input: n = 2, k = 2 Output: 1 Explanation: row 1: 0 row 2: 01
Constraints:
1 <= n <= 301 <= k <= 2n - 1Problem 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.
This approach utilizes the recursive nature of the transformation of each row. We start from the nth row and trace back to see which position in the previous level gives us the current k-th position.
The function kthGrammar is defined recursively. For each call, it checks if n is 1, in which case it returns 0 since the first row is always 0.
Otherwise, it calculates the midpoint, which is 2^(n-2). It then compares k with this midpoint to determine whether to explore the first half (which is the same as the previous row) or the second half (which is the inverse of the previous row).
Time Complexity: O(n), as each recursive call reduces the problem size by a constant factor.
Space Complexity: O(n), due to the recursion stack.
The iterative approach to solve this problem is based on tracing the path from the kth element in the nth row back to the root (1st element of the 1st row). Depending on whether k is odd or even, we determine whether to toggle the current result bit as we move up levels until we arrive at the base case.
This implementation initializes a variable result to 0 as we start tracing from the bottom. For each level, based on whether k is odd or even, we might toggle the bit stored in result. We keep shifting k up till it equals 1.
Time Complexity: O(n).
Space Complexity: O(1), as no additional space is used outside of constant variables.
Let's first observe the pattern of the first few rows:
n = 1: 0
n = 2: 0 1
n = 3: 0 1 1 0
n = 4: 0 1 1 0 1 0 0 1
n = 5: 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
...
We can see that the first half of each row is exactly the same as the previous row, and the second half is the inversion of the previous row. Note that "inversion" here means changing 0 to 1 and 1 to 0.
If k is in the first half, then the k-th character is the same as the k-th character of the previous row, so we can directly recurse with kthGrammar(n - 1, k).
If k is in the second half, then the k-th character is the inversion of the (k - 2^{n - 2})-th character of the previous row, i.e., kthGrammar(n - 1, k - 2^{n - 2}) \oplus 1.
The time complexity is O(n), and the space complexity is O(n).
Python
Java
C++
Go
TypeScript
In the problem, the index starts from 1. We will change k to k-1, converting the index to start from 0. In the following discussion, all indices start from 0.
Upon closer observation, the i-th character in a row generates two characters at positions 2i and 2i+1 in the next row.
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
If the i-th character is 0, then the characters generated at positions 2i and 2i+1 are 0 and 1, respectively. If the i-th character is 1, the generated characters are 1 and 0.
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
^ * *
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
^ * *
We can see that the character at position 2i (even index) is always the same as the character at position i, while the character at position 2i+1 (odd index) is the inversion of the character at position i. In other words, characters at odd indices are always the result of one inversion. If the number of inversions is even, the character remains unchanged; if the number of inversions is odd, it is equivalent to one inversion.
Therefore, we only need to check whether k is odd. If it is, we accumulate one inversion. Then, we divide k by 2 and continue to check, accumulating the number of inversions until k becomes 0.
Finally, we determine whether the number of inversions is odd. If it is, the answer is 1; otherwise, it is 0.
The process of accumulating the number of inversions is essentially equivalent to counting the number of 1s in the binary representation of k.
The time complexity is O(log k), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), as each recursive call reduces the problem size by a constant factor. |
| Iterative Approach | Time Complexity: O(n). |
| Recursion | — |
| Bit Manipulation + Brain Teaser | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Parent Tracking | O(n) | O(n) | Best for explaining the grammar relationship between rows during interviews |
| Iterative Flip Counting | O(n) | O(1) | Preferred when avoiding recursion or when memory usage must remain constant |
K-th Symbol in Grammar | Recursion | Recurrence Relation Explained | GOOGLE | Leetcode - 779 • codestorywithMIK • 23,009 views views
Watch 9 more video solutions →Practice K-th Symbol in Grammar with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor