Daily LeetCode Problems: 779 :K-th Symbol in Grammar

“K-th Symbol in Grammar.” This problem revolves around constructing a table of rows using a unique pattern of 0s and 1s. We’ll explore the problem statement, decipher the pattern, and provide an efficient solution to determine the k-th symbol in the nth row of the table.

Problem Statement:

In this problem, we are tasked with constructing a table of rows in the following manner:

Start with the first row containing a single ‘0’.
In every subsequent row, replace each ‘0’ in the previous row with ‘01’, and each ‘1’ with ‘10’.

Our goal is to find the k-th symbol in the nth row (both 1-indexed) of the table.

Approach:

To solve this problem, we need to understand the pattern and recurrence that emerges as we construct the rows.

The key insight is that the construction process can be thought of as a binary tree. The initial ‘0’ is the root, and each ‘0’ in a row has two children (‘0’ and ‘1’) in the row below, while each ‘1’ in a row has two children (‘1’ and ‘0’) in the row below. The tree branches out in a balanced manner.

With this insight, we can use a recursive approach to traverse the tree and find the k-th symbol in the nth row. We start with the root and move down the tree based on whether k is on the left or right side of the current node.

Pseudocode:

def kthGrammar(n, k):
    # Base case: if n is 1, the first row contains only '0'.
    if n == 1:
        return 0

    # Calculate the midpoint of the row, where the tree branches.
    mid = 2**(n-1) // 2

    # If k is in the left subtree, recurse on the left child.
    if k <= mid:
        return kthGrammar(n - 1, k)
    else:
        # If k is in the right subtree, recurse on the right child and flip the result.
        return 1 - kthGrammar(n - 1, k - mid)

Complexity Analysis:

Let’s analyze the complexity of our solution:

Time complexity: The time complexity of this solution is O(log k), where k is the index of the symbol we want to find. This is because the problem reduces by half with each recursive call.
Space complexity: The space complexity is O(log n) due to the recursive call stack.

Full Solution

Python

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        if n == 1:
            return 0
        length = 2 ** (n - 2)
        if k <= length:
            return self.kthGrammar(n - 1, k)
        else:
            return 1 - self.kthGrammar(n - 1, k - length)

Java

class Solution {
  public int kthGrammar(int n, int k) {
    if (n == 1)
      return 0;
    if (k % 2 == 1)
      return kthGrammar(n - 1, (k + 1) / 2) == 0 ? 0 : 1; // Left node
    return kthGrammar(n - 1, k / 2) == 0 ? 1 : 0;         // Right node
  }
}