LeetCode 89: Gray Code Solution in Python Explained

Problem Statement

In LeetCode 89, you’re given an integer n representing the number of bits. Your task is to return a Gray code sequence: a list of 2ⁿ integers (0 to 2ⁿ-1) where each consecutive pair differs by exactly one bit, and the first and last may differ by one bit too. This differs from array merging like LeetCode 88: Merge Sorted Array, focusing on binary patterns.

Constraints

• 0 <= n <= 16

Example

Let’s see some cases:

Copy codeInput: n = 2
Output: [0,1,3,2]
Explanation: Binary: [00,01,11,10] - each pair differs by one bit (00->01, 01->11, 11->10).

Copy codeInput: n = 1
Output: [0,1]
Explanation: Binary: [0,1] - differs by one bit.

Copy codeInput: n = 0
Output: [0]
Explanation: Single value, no pairs to differ.

These examples show the goal: a sequence with single-bit transitions.

Understanding the Problem

How do you solve LeetCode 89: Gray Code in Python? Take n = 2. We need 2² = 4 numbers (0 to 3) where each pair differs by one bit: [0,1,3,2] works (00 -> 01 -> 11 -> 10). This isn’t a string scramble like LeetCode 87: Scramble String; it’s about generating a binary sequence. We’ll use: 1. Reflection Method: O(2ⁿ) time, O(1) extra space—our top pick. 2. Bit Manipulation: O(2ⁿ) time, O(1) extra space—a clever shortcut.

Let’s dive into the primary solution.

Solution 1: Reflection Method Approach (Primary)

Explanation

Gray code can be built recursively by reflecting the sequence for n-1 and adding 2ⁿ⁻¹ to the reflected part. For n=1, it’s [0,1]. For n=2, take [0,1], reflect to [1,0], add 2¹=2 to the reflected part [3,2], and combine: [0,1,3,2]. This ensures each step differs by one bit.

For n = 2:

• n=1: [0,1].
• Reflect: [1,0].
• Add 2: [3,2].
• Combine: [0,1,3,2].

Step-by-Step Example

Example 1: n = 2

Goal: Return [0,1,3,2].

• Start: result = [0].
• Step 1: i = 0 (bit 0).
• Reflect: [0].
• Add 2⁰=1: [1].
• result = [0,1].
• Step 2: i = 1 (bit 1).
• Reflect: [1,0].
• Add 2¹=2: [3,2].
• result = [0,1,3,2].
• Finish: Return [0,1,3,2].

Example 2: n = 1

Goal: Return [0,1].

• Start: result = [0].
• Step 1: i = 0.
• Reflect: [0].
• Add 2⁰=1: [1].
• result = [0,1].
• Finish: Return [0,1].

Example 3: n = 0

Goal: Return [0].

• Start: result = [0].
• Step 1: No iterations (range(0)).
• Finish: Return [0].

How the Code Works (Reflection Method) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef grayCode(n: int) -> list[int]:
    # Line 1: Initialize result with the base case
    result = [0]
    # Starts with [0], the Gray code for n=0
    # This is the foundation we’ll build upon

    # Line 2: Iterate over each bit position
    for i in range(n):
        # i goes from 0 to n-1 (e.g., for n=2, i=0,1)
        # Each iteration adds the next bit’s contribution

        # Line 3: Get the current length of result
        curr_len = len(result)
        # Stores the number of elements before reflection (e.g., 1 for [0], 2 for [0,1])
        # Used to iterate over existing elements in reverse

        # Line 4: Reflect and add 2^i to the reflected part
        for j in range(curr_len - 1, -1, -1):
            # j iterates over result in reverse (e.g., for [0,1], j=1,0)
            # Reflects the sequence by processing from end to start

            # Line 5: Calculate the new value
            new_val = result[j] + (1 << i)
            # Adds 2^i to the current value (e.g., i=0, 1<<0=1, 0+1=1; i=1, 1<<1=2, 1+2=3)
            # 1 << i is a bit shift, giving 2^i (e.g., 1, 2, 4 for i=0,1,2)
            # This creates the reflected part with the new bit set

            # Line 6: Append the new value to result
            result.append(new_val)
            # Adds the new value to the end (e.g., append 1 to [0], append 3 to [0,1])
            # Builds the sequence incrementally

    # Line 7: Return the complete Gray code sequence
    return result
    # Returns the final list (e.g., [0,1,3,2] for n=2)
    # Contains 2^n elements, each differing by one bit from its neighbors

This detailed explanation clarifies how reflection builds the sequence efficiently.

Alternative: Bit Manipulation Approach

Explanation

A Gray code number can be generated directly from its binary index using the formula i ^ (i >> 1), where ^ is XOR and >> 1 shifts right by 1. For n=2, compute 0 to 3: 0^0=0, 1^0=1, 2^1=3, 3^1=2.

For n = 2:

• 0: 00 ^ 00 = 00 (0).
• 1: 01 ^ 00 = 01 (1).
• 2: 10 ^ 01 = 11 (3).
• 3: 11 ^ 01 = 10 (2).

Result: [0,1,3,2].

Step-by-Step Example (Alternative)

For n = 2:

• i=0: 0 ^ 0 = 0.
• i=1: 1 ^ 0 = 1.
• i=2: 2 ^ 1 = 3.
• i=3: 3 ^ 1 = 2.
• Finish: [0,1,3,2].

How the Code Works (Bit Manipulation)

Copy codedef grayCodeBit(n: int) -> list[int]:
    return [i ^ (i >> 1) for i in range(1 << n)]

Complexity

• Reflection Method:
• Time: O(2ⁿ) – generates 2ⁿ elements.
• Space: O(1) – extra space, excluding output.
• Bit Manipulation:
• Time: O(2ⁿ) – computes 2ⁿ elements.
• Space: O(1) – extra space, excluding output.

Efficiency Notes

Both are O(2ⁿ) time (required to generate 2ⁿ elements), but Reflection Method is more intuitive, while Bit Manipulation is concise and elegant—Reflection is preferred for understanding the pattern.

Key Insights

• Reflection: Builds via symmetry.
• Single Bit: XOR ensures one-bit difference.
• Sequence Size: Always 2ⁿ elements.

Additional Example

For n = 3:

• Goal: [0,1,3,2,6,7,5,4].
• Reflection: [0,1] -> [0,1,3,2] -> [0,1,3,2,6,7,5,4].

Edge Cases

• n = 0: [0] – single value.
• n = 1: [0,1] – basic pair.
• Large n: n=16 → 65,536 elements, still O(2ⁿ).

Both solutions handle these seamlessly.

Final Thoughts

LeetCode 89: Gray Code in Python is a fascinating dive into binary sequences. The Reflection Method offers a clear construction, while Bit Manipulation is a sleek shortcut. Want more? Try LeetCode 90: Subsets II for combinatorial fun or LeetCode 88 for array merging. Ready to practice? Solve LeetCode 89 on LeetCode with n = 2, aiming for [0,1,3,2]—test your skills now!