Scale Engineer

K-th Symbol in Grammar

Med
#0733Time: O(2^n). The length of the string for row `i` is `2^(i-1)`. Building the string for row `i` takes O(2^(i-1)) time. The total time is the sum of these lengths, which is dominated by the final step, resulting in O(2^n) complexity.Space: O(2^n). We need to store the string for the `n`-th row, which has a length of `2^(n-1)`. This is infeasible for `n=30`.
Patterns
MathRecursionBit Manipulation

Prompt

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, 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 <= 30
  • 1 <= k <= 2n - 1

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We start with the string for the first row, "0", and iteratively generate the string for each subsequent row up to n. This method is straightforward but computationally expensive.

Algorithm

  • Initialize a string currentRow to "0".
  • Loop from i = 2 to n.
  • Inside the loop, create a StringBuilder for the next row.
  • Iterate through each character of currentRow.
  • If the character is '0', append "01" to the StringBuilder.
  • If the character is '1', append "10" to the StringBuilder.
  • After iterating, update currentRow to the string from the StringBuilder.
  • After the main loop finishes, currentRow holds the string for the n-th row.
  • The result is the character at index k-1. Convert the character '0' or '1' to an integer.

Walkthrough

The algorithm begins with the base case, row 1, which is simply "0". It then enters a loop that runs from row 2 to row n. In each iteration, it constructs the next row by scanning the current row. For every '0' encountered, it appends "01" to a new string builder, and for every '1', it appends "10". After the new row is fully constructed, it replaces the old row. This process continues until the n-th row is generated. Finally, it retrieves the character at the k-1-th index (since k is 1-indexed) and converts it to an integer to get the final answer.

class Solution {    public int kthGrammar(int n, int k) {        String currentRow = "0";        for (int i = 2; i <= n; i++) {            StringBuilder nextRow = new StringBuilder();            // The length of the string can become very large, so we might not even            // be able to build it for large n. This code is for demonstration.            for (char c : currentRow.toCharArray()) {                if (c == '0') {                    nextRow.append("01");                } else {                    nextRow.append("10");                }            }            currentRow = nextRow.toString();        }        return currentRow.charAt(k - 1) - '0';    }}

Complexity

Time

O(2^n). The length of the string for row `i` is `2^(i-1)`. Building the string for row `i` takes O(2^(i-1)) time. The total time is the sum of these lengths, which is dominated by the final step, resulting in O(2^n) complexity.

Space

O(2^n). We need to store the string for the `n`-th row, which has a length of `2^(n-1)`. This is infeasible for `n=30`.

Trade-offs

Pros

  • Simple to understand and directly follows the problem statement.

Cons

  • Highly inefficient for the given constraints (n <= 30).

  • Will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) on most platforms.

Solutions

class Solution {public  int kthGrammar(int n, int k) { return Integer.bitCount(k - 1) & 1; }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem