779. K-th Symbol in Grammar - Explanation

1. Brute Force

Intuition

The problem generates rows where each row is built from the previous one: 0 becomes 01 and 1 becomes 10. The most straightforward approach is to actually build each row until we reach row n, then return the character at position k. While simple to understand, this approach becomes impractical for large n since each row doubles in size.

Algorithm

Start with the first row containing just 0.
For each subsequent row up to n:
- Create a new row by replacing each 0 with 01 and each 1 with 10.
Return the character at index k - 1 from the final row.

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        prev = ['0']
        for i in range(2, n + 1):
            cur = []
            for c in prev:
                if c == '0':
                    cur.append('0')
                    cur.append('1')
                else:
                    cur.append('1')
                    cur.append('0')
            prev = cur
        return int(prev[k - 1])

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(2 ^ n)$

2. Binary Tree Traversal (Recursion)

Intuition

We can visualize the grammar as a binary tree where each node generates two children. The key insight is that the position k in row n has a parent at position ceil(k/2) in row n-1. If k is in the left half of the current row, it inherits the parent's value directly. If k is in the right half, its value is the flip of the parent. This lets us trace from position k back to the root without building any rows.

Algorithm

Define a recursive function dfs(n, k, root) where root tracks the current value.
Base case: if n == 1, return the current root value.
Calculate total = 2^(n-1), the size of row n.
If k > total / 2, we're in the right half:
- Recurse with n - 1, adjust k by subtracting half, and flip root using XOR.
Otherwise, recurse with the same root value.
Start with dfs(n, k, 0) since row 1 starts with 0.

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        def dfs(n, k, root):
            if n == 1:
                return root

            total = 1 << (n - 1)
            if k > (total // 2):
                return dfs(n - 1, k - (total // 2), root ^ 1)
            else:
                return dfs(n - 1, k, root)

        return dfs(n, k, 0)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Binary Tree Traversal (Iteration)

Intuition

This is the iterative version of the binary tree approach. Instead of recursion, we use a loop to perform binary search on the position. We maintain a range [left, right] representing the current segment and track whether the value flips as we narrow down to position k. Each iteration halves the search space until we've processed all n - 1 levels.

Algorithm

Initialize cur = 0 (the root value) and set left = 1, right = 2^(n-1).
Loop n - 1 times:
- Calculate mid = (left + right) / 2.
- If k <= mid, narrow to the left half by setting right = mid.
- Otherwise, narrow to the right half, set left = mid + 1, and flip cur.
Return cur as the final answer.

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        cur = 0
        left, right = 1, 2 ** (n - 1)

        for _ in range(n - 1):
            mid = (left + right) // 2
            if k <= mid:
                right = mid
            else:
                left = mid + 1
                cur = 0 if cur else 1

        return cur

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

4. Recursion (Traverse Towards Root)

Intuition

Each position in row n comes from a parent position in row n-1. If position k is odd, it's a left child and has the same value as its parent at position (k+1)/2. If k is even, it's a right child and has the opposite value. We recursively trace back to row 1 (which is always 0) and determine the value based on how many flips occurred.

Algorithm

Base case: if n == 1, return 0.
If k is odd, return kthGrammar(n - 1, (k + 1) / 2) since left children inherit parent value.
If k is even, return kthGrammar(n - 1, k / 2) XOR 1 since right children flip.

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        if k & 1:
            return self.kthGrammar(n - 1, (k + 1) // 2)
        return self.kthGrammar(n - 1, k // 2) ^ 1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

5. Math

Intuition

There's an elegant mathematical pattern here. The value at position k depends on how many times we flip while tracing from k back to the root. Each flip happens when we're a right child, which corresponds to a 1 bit in the binary representation of k - 1. So the answer is simply the parity (odd or even) of the number of 1 bits in k - 1.

Algorithm

Convert k - 1 to binary.
Count the number of 1 bits.
Return the count modulo 2 (i.e., count & 1).

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        return bin(k - 1).count('1') & 1

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$ or $O(\log n)$ depending on the language.

Common Pitfalls

Using 0-Indexed vs 1-Indexed Position

The problem uses 1-indexed positions for k, but many solutions require converting to 0-indexed logic. A common mistake is forgetting to subtract 1 when counting bits or when comparing positions. For the bit-counting solution, you must use k - 1 (not k) to correctly count the number of flips from the root.

Integer Overflow When Computing Row Size

When calculating the size of row n as 2^(n-1), this can overflow for large values of n (up to 30 in the constraints). Using 1 << (n - 1) is safe in most languages for n <= 30, but be careful with signed 32-bit integers when n = 31 or higher. Always ensure your bit-shift operations use appropriate integer types.

Confusing Left Child vs Right Child Logic

In the recursive solutions, the logic for determining whether a position is a left child or right child is subtle. Left children (odd k values) inherit the parent's value, while right children (even k values) flip it. Mixing up this logic or incorrectly computing the parent position (k + 1) / 2 vs k / 2 leads to wrong answers.