Gray Code: Building a Cube One Bit at a Time

Some LeetCode problems are memorable because they teach an algorithm. This one stayed with me for a different reason: it started as a confusing ordering problem and ended as a tour through geometry, recursion, and one surprisingly small bitwise formula.

This is the path I followed while solving Gray Code — LeetCode 89.

1. Gray codes and Gray cubes

A Gray code is an ordering of binary words in which two consecutive words differ in exactly one bit. For example, 01 → 11 is a valid step because only the left bit changes; 01 → 10 is not.

There is a geometric way to see the same definition. Take the hypercube graph \(Q_d\):

• each vertex is one of the \(2^d\) binary words of length \(d\);
• two vertices share an edge exactly when their words differ in one bit.

A cyclic Gray code is therefore a cycle that visits every vertex of \(Q_d\) exactly once—a Hamiltonian cycle through the Boolean cube. This was the first idea that made the problem feel visual rather than arbitrary.

The cubes grow recursively

Every new dimension is made from two copies of the previous dimension. Prefix the first copy with 0, prefix the second with 1, and connect matching vertices.

The same construction appears in the codes. If \(G_d\) is a Gray code for dimension \(d\), then the reflected recurrence is

where prefixing a list means prefixing every word in that list, and \(\Vert\) means concatenation.

The blue half is the old order. The violet half is its reflection. That reversal will turn out to be the detail that makes everything work.

What LeetCode asks for

Given n, return all \(2^n\) integers from 0 through \(2^n-1\), starting with 0, without repetition, so that every adjacent pair differs in exactly one bit. The final and first values must differ by one bit too, so the result closes into a cycle.

What should the result look like?

One bit

For n = 1, there are only two values:

Input:  n = 1
Output: [0, 1]

In binary, the cycle is simply 0 → 1 → 0. Its only bit changes on both transitions.

Two bits

For n = 2, one valid answer is:

Input:  n = 2
Output: [0, 1, 3, 2]

The decimal values can hide the pattern, so let us read the same result in binary.

There may be more than one correct result. For example, [0, 2, 3, 1] is also valid for n = 2. LeetCode accepts any sequence satisfying all five rules.

A larger expected result

With n = 3, we need all eight values. One valid sequence is:

[0, 1, 3, 2, 6, 7, 5, 4]

Notice that the repeated 0 in the final row is only there to visualize the closing edge; it is not included a second time in the returned array.

2. My first idea: group by the number of ones

At first the problem looked much harder than its statement. If I ignored the binary representation, I was left trying to permute \(2^n\) integers under a condition that felt difficult to control.

My first instinct was to group numbers by their number of set bits. A one-bit move always changes the number of ones by exactly one, so perhaps I could distribute the values layer by layer.

For n = 3, the layers look like this:

There are \(\binom{n}{k}\) values containing exactly \(k\) ones, so the groups do not have equal sizes. Worse, knowing that the next value belongs to the neighboring layer tells me only its weight, not which exact bit should change. The grouping exposes the cube’s bipartite structure, but it does not give me the tour.

I needed a stronger structure. That is when the recurrence came back to mind:

If I already know how to walk through a \(d\)-cube, can I use that walk to build one through a \((d+1)\)-cube?

Two segments, one square

Start with the one-dimensional answer [0, 1]. A square is just two copies of this segment living in a two-bit world:

The left copy receives a leading 0. The right copy receives a leading 1. But if I keep both copies in the same direction, the middle jump is 01 → 10, which flips two bits. The fix is beautifully small: walk through the second copy backwards.

Now every kind of edge is safe:

• inside either copy, the inductive solution changes one bit;
• between the copies, only the new leading bit changes;
• the reflected order also makes the last word adjacent to the first.

This explains the entire point → segment → square → cube animation above. A \((d+1)\)-cube is two translated \(d\)-cubes joined vertex to corresponding vertex.

The recursive construction

In integer form, prefixing 0 changes nothing. Prefixing 1 sets bit d, which adds \(2^d\). Iterating over the existing answer backwards performs the reflection:

impl Solution {
    pub fn gray_code(n: i32) -> Vec<i32> {
        let mut gray = vec![0];

        for bit in 0..n {
            let leading_bit = 1 << bit;

            for i in (0..gray.len()).rev() {
                gray.push(leading_bit | gray[i]);
            }
        }

        gray
    }
}

At round bit, the list doubles, so the total work is

The time complexity is therefore \(O(2^n)\) and the returned array occupies \(O(2^n)\) space. This is optimal in the output-sensitive sense: we cannot return \(2^n\) values in less than \(O(2^n)\) time.

3. The clever solution I found afterward

The recursive construction was satisfying because I could see why it worked. Then, while reading other solutions, I found that the whole reflected construction could be compressed into one expression:

In words: XOR the ordinary binary index with a copy shifted one position to the right.

Why does it work? Each Gray bit records whether two neighboring bits of i are different. When i increases, the usual binary carry may flip a whole suffix such as 0111 → 1000; after the XOR, those coordinated flips collapse into a change at exactly one Gray bit. The formula is the bitwise shadow of the reflection we constructed geometrically.

The LeetCode solution becomes almost suspiciously short:

impl Solution {
    pub fn gray_code(n: i32) -> Vec<i32> {
        (0..(1 << n))
            .map(|i| i ^ (i >> 1))
            .collect()
    }
}

We still generate \(2^n\) values, so the complexity remains \(O(2^n)\) time and \(O(2^n)\) output space. Apart from the returned vector, this version uses only \(O(1)\) auxiliary space.

What I am taking from this problem

The one-line solution is clever, but it is not the part I enjoyed most. The rewarding part was watching the object reveal itself: an awkward permutation became a walk on a graph; the graph became two smaller cubes; and the recursive reflection finally became an XOR.

That is why solving problems—and sometimes getting stuck on them—is fun. The final code may be four lines, while the path to those four lines can contain geometry, combinatorics, induction, and a new way of looking at bits.

Thank you, LeetCode, for a small problem with a surprisingly large cube hidden inside it.