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
Difficulty
and has an acceptance rate of about 66% (600k+ submissions).
Typical patterns to solve this problem:
- Backtracking
- Bit Manipulation
- Math
AI Disclaimer
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.
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:
maskis computed as2 ** size. This value corresponds to a binary number with a single1in the position that becomes the new most-significant bit for the next level.sizeis incremented to reflect the addition of a new bit.nextis assigned to the existingresultlist, allowing the algorithm to extend the list in place.- The
forloop iterates over a reversed view of the current sequence. For each elementi, it appendsi + masktonext. Addingmaskeffectively sets the new most-significant bit to1while preserving the lower bits ofi. 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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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++ |
Videos
Similar Problems
- problem 717: 1-bit and 2-bit Characters
Solved On The Same Day
- problem 195: Tenth Line
- problem 53: Maximum Subarray
- problem 56: Merge Intervals
- problem 78: Subsets
- problem 86: Partition List
- problem 90: Subsets II
- problem 98: Validate Binary Search Tree
- problem 179: Largest Number
- problem 456: 132 Pattern
- problem 473: Matchsticks to Square
- problem 542: 01 Matrix
- problem 916: Word Subsets
- problem 1930: Unique Length-3 Palindromic Subsequences
- problem 233: Number of Digit One
- problem 295: Find Median from Data Stream
- problem 315: Count of Smaller Numbers After Self
Extra
- 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