Problem 89

Abstract / Summary

Generate a sequence of binary numbers where each consecutive pair differs by exactly one bit.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0089.py

class Solution:
    def grayCode(self, n: int) -> List[int]:
        # https://en.wikipedia.org/wiki/Gray_code
        result = [ 0, 1 ]
        size = 1
        while size < n:
            mask = 2 ** size
            size += 1
            next = result
            for i in reversed(result):
                next.append(i + mask)

            result = next

        return result
15 lines | 397 bytes | submitted August 17, 2023 | GitHub   8% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 66% (600k+ submissions).

Typical patterns to solve this problem:
  • Backtracking
  • Bit Manipulation
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation generates the binary reflected Gray code sequence for a given number of bits n. It starts with the base sequence for one bit and iteratively expands it until the desired length is reached. The algorithm follows the classic construction described in the Gray code literature, building each new level by reflecting the current sequence and prefixing the reflected part with a leading 1 in the new most-significant position.

Key Steps

Initialization of the base sequence

result = [0, 1]
size = 1

The algorithm begins with the two-element Gray code for a single bit: 0 and 1. The variable size tracks the current number of bits represented in result.

Loop that expands the sequence

while size < n:
    mask = 2 ** size
    size += 1
    next = result
    for i in reversed(result):
        next.append(i + mask)
    result = next

The loop continues until the sequence covers n bits. Inside each iteration:

  • mask is computed as 2 ** size. This value corresponds to a binary number with a single 1 in the position that becomes the new most-significant bit for the next level.
  • size is incremented to reflect the addition of a new bit.
  • next is assigned to the existing result list, allowing the algorithm to extend the list in place.
  • The for loop iterates over a reversed view of the current sequence. For each element i, it appends i + mask to next. Adding mask effectively sets the new most-significant bit to 1 while preserving the lower bits of i. Because the iteration proceeds in reverse order, the appended values appear in the required reflected order.

Return of the final sequence

return result

After the loop terminates, result contains the complete Gray code sequence for n bits and is returned to the caller.

Edge Cases Handled

When n equals 1, the loop condition size < n is false from the start, so the method returns the initial list [0, 1], which is the correct Gray code for a single bit. For any n greater than 1, the loop executes exactly n-1 times, each time correctly extending the sequence by reflecting and prefixing with the appropriate mask. The use of reversed(result) ensures that the reflected half is generated in the proper order, even when the original list grows large.

Performance Optimizations

The algorithm avoids allocating a new list for the reflected half on each iteration. By assigning next = result and then appending to next while iterating over a reversed snapshot of result, it reuses the existing list storage. This in-place extension reduces memory churn and improves cache locality because the list grows continuously rather than being recreated repeatedly.

The iterative approach eliminates the overhead of recursive calls, keeping the call stack shallow regardless of the value of n. Computing the mask with exponentiation (2 ** size) is a constant-time arithmetic operation, and the loop body performs only simple integer addition and list appends, which are highly optimized in the underlying runtime.

Overall, the implementation builds the Gray code sequence in a linear fashion with respect to the number of generated elements, leveraging in-place list growth and a minimal set of arithmetic operations to achieve efficient execution.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a row of numbers written out. A gray code is a special way of listing numbers where each step only changes one tiny thing. Think of it like a magic dance where you only move one toe at a time. The code starts with just two small numbers, zero and one. Then it looks at those numbers and mirrors them. It takes the ones it already has and adds a new, bigger piece to the front of the copies. It puts these two groups together to make a new, longer list. The computer repeats this dance over and over again, making the list of numbers grow bigger and bigger each time, until it has all the numbers it needs. It is like building a tower of blocks where every new level is built by copying the level below and adding a special block to change it just enough to be different. Each step makes sure that the new numbers are very similar to the ones that came right before them.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 6.30 | σ = 1.24

Complexity Analysis

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java JS Go
LeetcodeHelp C++ Python Java
MemoryLimitExceeded C++ Python
Progiez C++ Python Java
github aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++
charles-wangkai Java
chenyanzhe C++
everthis JS
fsq C++
gaosq0604 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JS
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
lzl124631x C++
qiyuangong Python
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
wisdompeak C++
XiaotaoGuo C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python
LeetcodeHelp C++, Java, Python
MemoryLimitExceeded Python, C++
Progiez C++, Java, Python
aylei Rust
begeekmyfriend C
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
chenyanzhe C++
everthis JavaScript
fsq C++
gaosq0604 Python
gouthampradhan Java
halfrost Go
haoel C++
JoshCrozier JavaScript
keineahnung2345 C++
lennylxx C
linouk23 C++
lkwq007 Python
luangong C++
lzl124631x C++
qiyuangong Python
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
vli02 C
wisdompeak C++
XiaotaoGuo C++
47 links | 33 authors | 9 languages

Videos

9 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

1 easy 12 medium 3 hard
17 solutions   August 17, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality