89. Gray Code
Model: qwen3.5:9b
Topics: Backtracking
FAANG asked: 0
Acceptance rate: 50.7%
Problem Breakdown
We need to generate a sequence of integers representing Gray codes for n bits. The output must be an array where the first element is always 0. Crucially, every adjacent pair in this list (including wrapping around if considered cyclic) differs by exactly one bit position. Given constraints , we need to handle up to elements (), which fits comfortably within standard memory limits but requires an efficient generation strategy rather than brute-force permutation checking.
Intuition
A naive approach would be to generate all possible binary numbers of length n and try permutations until we find one satisfying the adjacency constraint. This is infeasible because there are potential orderings, making it exponential or factorial time complexity relative to .
Instead, observe small cases:
- For , sequence is
[0, 1](binary0,1). - For , we can extend the previous list. If we take our current valid Gray code for bits and prefix a
0to all elements, then reverse that list and prefix a1to each element, we maintain the single-bit difference property. The reversal ensures that when traversing back from high values to low values in the new bit dimension, only the MSB flips while lower bits traverse their previous sequence backwards (which is valid since they differ by one bit). This recursive reflection pattern allows us to construct the solution iteratively without searching or checking constraints at every step.
Approach
We will use an iterative construction based on the reflection property derived in intuition:
- Initialize a list with
[0]. - Iterate from
bit = 1up to . In each iteration, we double the size of our current sequence (since adding one bit doubles the number of states). - For every element currently in the list, append it unchanged (effectively prefixing a
0). - Then iterate through the reversed version of the current list and for each element, add the value with the new MSB set (
element | bit), appending these to our result. - This ensures we traverse all combinations where only one bit changes between steps.
Complexity Analysis
- Time: . We perform a constant amount of work for each element in the output list, and there are exactly elements required by definition. The total number of append operations across all iterations equals the final sequence length.
- Space: to store the result array itself. If implemented recursively without iteration optimization, we would add an additional stack space proportional to
n, but our iterative approach keeps auxiliary space minimal relative to the output size.
Solution
def grayCode(n: int) -> list[int]:
# Start with base case for 0 bits (conceptually), represented as [0]
res = [0]
# Iterate through each bit position from 1 up to n
current_bit_value = 1
while len(res) < (1 << n):
# To maintain Gray code property when adding a new MSB:
# We take the existing sequence, keep it as is (MSB=0),
# then reverse and add with MSB=1.
# Create reversed copy of current list to append high-bit values in correct order
for x in res[::-1]:
res.append(x | current_bit_value)
# Shift the bit mask left by 1 (equivalent to doubling value: 2^k -> 2^(k+1))
current_bit_value <<= 1
return res
# Example usage matching constraints
print(grayCode(2))
Edge Cases Handled
- Minimum
n(): The loop runs once, doubling[0]to[0, 1], which satisfies the constraint. - Maximum
n(): Generates integers; Python handles large lists and integer values without overflow issues within this range (values fit in standard machine words). - Starting Value: The algorithm initializes with
[0], guaranteeing the sequence always starts at 0 as required.