K-th Symbol in Grammar solution and explanation
Google
9 more videos on this problem
Kth Symbol in GrammarAditya Verma · 23:32 · 154K views
K-th Symbol in Grammar | Recursion | Recurrence Relation Explained | GOOGLE | Leetcode - 779codestorywithMIK · 29:34 · 27K views
K-th Symbol in Grammar - Leetcode 779 - PythonNeetCodeIO · 10:19 · 19K views
Recursion Interview Question - "Kth Symbol in Grammar" (Data Structures & Algorithms)Potato Coders · 8:27 · 13K views
leetCode 779 - K-th Symbol in Grammar - Recursion, Tail Recursion | JSer - algorithm & JavaScriptJSer · 15:03 · 1K views
Lecture 8 : Kth Symbol in Grammar | LeetCode 779 | Recursion Phod DengeCODE SHARK · 16:24 · 825 views
Cracking the Code: Unveiling the K-th Symbol in Grammar | LeetCode 779 Solutions in PythonvanAmsen · 8:30 · 719 views
Solving LeetCode Question 779 | K-th Symbol in Grammar Live with Vivek, ex-SDE at AmazonProgramming Pathshala · 1:04:07 · 587 views
LeetCode 779 K th Symbol in GrammarMaxMing · 2:53 · 526 views
Code EveryDay | Recursion | Asked in: Amazon, Goldman Sachs | 779 K-th Symbol in GrammarProgramming Pathshala · 39:22 · 299 views
The problem
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.
- For example, for
n = 3, the1strow is0, the2ndrow is01, and the3rdrow is0110.
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 - 1
Approach overview
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.
Approach 1: Recursive Approach
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.
def kthGrammar(n, k):
if n == 1:
return 0
mid = 1 << (n - 2)
if k <= mid:
return kthGrammar(n - 1, k)
else:
return 1 - kthGrammar(n - 1, k - mid)
print(kthGrammar(3, 2)) # Output: 1public class KthSymbol {
public int kthGrammar(int n, int k) {
if (n == 1) return 0;
int mid = 1 << (n - 2);
if (k <= mid) {
return kthGrammar(n - 1, k);
} else {
return 1 - kthGrammar(n - 1, k - mid);
}
}
public static void main(String[] args) {
KthSymbol symbol = new KthSymbol();
System.out.println(symbol.kthGrammar(3, 2)); // Output: 1
}
}#include <iostream>
using namespace std;
int kthGrammar(int n, int k) {
if (n == 1) return 0;
int mid = (1 << (n - 2));
if (k <= mid) {
return kthGrammar(n - 1, k);
} else {
return 1 - kthGrammar(n - 1, k - mid);
}
}
int main() {
cout << kthGrammar(3, 2) << endl; // Output: 1
return 0;
}function kthGrammar(n, k) {
if (n === 1) return 0;
const mid = 1 << (n - 2);
if (k <= mid) {
return kthGrammar(n - 1, k);
} else {
return 1 - kthGrammar(n - 1, k - mid);
}
}
console.log(kthGrammar(3, 2)); // Output: 1#include <stdio.h>
int kthGrammar(int n, int k) {
if (n == 1) return 0;
int mid = (1 << (n - 2));
if (k <= mid) {
return kthGrammar(n - 1, k);
} else {
return 1 - kthGrammar(n - 1, k - mid);
}
}
int main() {
printf("%d\n", kthGrammar(3, 2)); // Output: 1
return 0;
}using System;
class KthSymbol {
public int KthGrammar(int n, int k) {
if (n == 1) return 0;
int mid = 1 << (n - 2);
if (k <= mid) {
return KthGrammar(n - 1, k);
} else {
return 1 - KthGrammar(n - 1, k - mid);
}
}
static void Main() {
KthSymbol symbol = new KthSymbol();
Console.WriteLine(symbol.KthGrammar(3, 2)); // Output: 1
}
}This function checks whether the index k falls within the first or second half of the row. If it's the first half, it calls itself to check in the (n-1)th row directly. Otherwise, it computes for the corrected position in the (n-1)th row and returns the opposite bit.
Time Complexity: O(n).
Space Complexity: O(n), due to recursion call stack.
Approach 2: Iterative Approach
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.
def kthGrammarIterative(n, k):
result = 0
while k > 1:
if k % 2 == 0:
result = 1 - result
k = (k + 1) // 2
return result
print(kthGrammarIterative(3, 2)) # Output: 1public class KthSymbolIterative {
public int kthGrammarIterative(int n, int k) {
int result = 0;
while (k > 1) {
if (k % 2 == 0) {
result = 1 - result;
}
k = (k + 1) / 2;
}
return result;
}
public static void main(String[] args) {
KthSymbolIterative symbol = new KthSymbolIterative();
System.out.println(symbol.kthGrammarIterative(3, 2)); // Output: 1
}
}#include <iostream>
using namespace std;
int kthGrammarIterative(int n, int k) {
int result = 0;
while (k > 1) {
if (k % 2 == 0) {
result = 1 - result;
}
k = (k + 1) / 2;
}
return result;
}
int main() {
cout << kthGrammarIterative(3, 2) << endl; // Output: 1
return 0;
}function kthGrammarIterative(n, k) {
let result = 0;
while (k > 1) {
if (k % 2 === 0) {
result = 1 - result;
}
k = Math.floor((k + 1) / 2);
}
return result;
}
console.log(kthGrammarIterative(3, 2)); // Output: 1#include <stdio.h>
int kthGrammarIterative(int n, int k) {
int result = 0;
while (k > 1) {
if (k % 2 == 0) {
result = 1 - result;
}
k = (k + 1) / 2;
}
return result;
}
int main() {
printf("%d\n", kthGrammarIterative(3, 2)); // Output: 1
return 0;
}using System;
class KthSymbolIterative {
public int KthGrammarIterative(int n, int k) {
int result = 0;
while (k > 1) {
if (k % 2 == 0) {
result = 1 - result;
}
k = (k + 1) / 2;
}
return result;
}
static void Main() {
KthSymbolIterative symbol = new KthSymbolIterative();
Console.WriteLine(symbol.KthGrammarIterative(3, 2)); // Output: 1
}
}The iterative solution directly computes from k's path towards the start using bit toggles when stepping back from even indexed positions. The loop continues until k equals 1.
Time Complexity: O(n).
Space Complexity: O(1), as only constant extra space is used.
Approach 3: Recursion
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).
function kthGrammar(n: number, k: number): number {
if (n == 1) {
return 0;
}
if (k <= 1 << (n - 2)) {
return kthGrammar(n - 1, k);
}
return kthGrammar(n - 1, k - (1 << (n - 2))) ^ 1;
}func kthGrammar(n int, k int) int {
if n == 1 {
return 0
}
if k <= (1 << (n - 2)) {
return kthGrammar(n-1, k)
}
return kthGrammar(n-1, k-(1<<(n-2))) ^ 1
}Approach 4: Bit Manipulation + Brain Teaser
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).
function kthGrammar(n: number, k: number): number {
return bitCount(k - 1) & 1;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func kthGrammar(n int, k int) int {
return bits.OnesCount(uint(k-1)) & 1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n). |
| Iterative Approach | Time Complexity: O(n). |
| Recursion | – |
| Bit Manipulation + Brain Teaser | – |
Complexity analysis
| 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 |
Frequently asked questions
Is K-th Symbol in Grammar easy or hard?
K-th Symbol in Grammar is generally considered a medium difficulty problem. The challenge comes from recognizing that you should not build the entire row, which would be exponential. Once you see the parent relationship and flip rule, the recursive or iterative solution becomes straightforward.
How to solve K-th Symbol in Grammar in O(n)?
Start from position k in row n and repeatedly move to its parent position (k+1)/2 in the previous row. If k is even, the value flips relative to the parent; if k is odd, it remains the same. Continue until reaching row 1 which contains 0, then apply the accumulated flips. This takes O(n) steps and constant extra space in the iterative version.
What is the best approach for K-th Symbol in Grammar?
The most common approach is recursive parent tracking. Each position in row n comes from a parent in row n-1, and even indices flip the parent value while odd indices keep it. This gives an O(n) time solution with O(n) recursion stack space. Many optimized implementations convert the same logic into an iterative O(1) space solution.
Is K-th Symbol in Grammar asked at Google/Amazon/Meta?
K-th Symbol in Grammar appears in interview preparation sets for major tech companies including Google, Amazon, and Meta. It tests recursion reasoning, binary tree style parent relationships, and bit manipulation insights, making it a common medium-level interview problem.
What data structure is used in K-th Symbol in Grammar?
The problem does not require building the full grammar string or using a complex data structure. Most solutions rely on recursion or iterative computation with simple integer operations. Conceptually, the grammar forms a binary tree structure where each node derives from a parent.
What is the time complexity of K-th Symbol in Grammar?
The typical recursive or iterative solution runs in O(n) time because you move from row n to row 1 step by step while determining the parent index. Space complexity is O(n) with recursion due to the call stack, or O(1) when implemented iteratively.
K-th Symbol in Grammar Python or Java solution approach?
Python and Java implementations usually follow the same logic: either a recursive function that calls k-th symbol for the parent index, or an iterative loop that tracks flips while reducing k to its parent. Both run in O(n) time and avoid constructing the exponentially large rows.