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 - 1This 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).
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1), as no additional space is used outside of constant variables.
| 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). |
L18. K-th Permutation Sequence | Leetcode • take U forward • 231,609 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