What is the brute force approach and complexity for Gray Code?

From 0, flip one bit at a time, never reuse a code, back up when stuck with time complexity O(N · 2^N) and space complexity O(2^N).

What is the optimal approach and complexity for Gray Code?

Code number i is i XOR (i shifted right by one); loop i from 0 to 2^n − 1 with optimal time complexity O(2^N) and space complexity O(1).

How do you identify the pattern for Gray Code?

Look for key signals in the prompt: "list all numbers from 0 to 2^n − 1" indicates The set of values is fixed, so only the order is free.; "neighbours differ in exactly one bit" indicates Each step is a single bit flip: XOR with one power of two.; "the first and last also differ in one bit" indicates The list must loop, so the wrap pair must be one flip apart too..

Gray Code

Medium·LeetCode #89Basic Anchor

LeetCode

Jump:

30-Second Mental ModelBitmask state — Gray code (one bit flips per step)

Complexity:O(N · 2^N)→O(2^N)

Key Insight

The i-th Gray code is i XOR (i >> 1): XOR the number with itself shifted right by one bit. Loop i from 0 to 2^n − 1 and output each code. There is no search and no visited array, because neighbours i and i + 1 always differ in one bit.

Core Validity Invariant

Use code(i) = i XOR (i >> 1) for every i from 0 to 2^n − 1. The codes are all different, and code(i) and code(i + 1) differ in exactly one bit, so the list is valid.

Problem

A Gray code is a list of all n-bit numbers in which every two neighbours differ in exactly one bit.

Build one for a given n. The list must hold every number from 0 to 2^n − 1, each one once, and it must start with 0. Any two neighbours in the list must differ in exactly one bit. The last number must also differ from the first (0) in exactly one bit, so the list can loop round.

Return any list that works.

Input

An integer n.

Output

A list of 2^n integers that forms a valid n-bit Gray code. Any valid list is accepted, so the answer is not unique.

Example 1

Input: n = 2

Output: [0, 1, 3, 2]

In binary the list is 00, 01, 11, 10. Each step flips one bit. The last step, 10 → 00, flips one bit too, so the list loops. [0, 2, 3, 1] is also accepted.

Example 2

Input: n = 1

Output: [0, 1]

0 and 1 differ in one bit. The step from 1 back to 0 closes the loop.

Constraints

• 1 ≤ n ≤ 16

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I list 0, 1, 2, 3 in plain order for n = 2, which neighbouring pair breaks the rule?
2.
The list has to hold every number from 0 to 2^n − 1. Does the order matter, or only which numbers appear?
3.
From one code, how many codes are exactly one bit away? Can I list the next choices without searching?
4.
Is there a rule that gives the i-th code directly, instead of building the list step by step?
5.
What must the last code be so that the list loops back to 0?

Brute force approach

Idea

Start at 0. From the current code, try flipping each of the n bits. Move to the first flip that gives a code you have not used yet, and keep going. If you get stuck before the list has 2^n codes, undo the last move and try the next bit. When the list is full, check that the last code is one bit away from 0.

Thinking process

1
A step may change only one bit. For n = 2, from 00 the next code is 01 (flip bit 0) or 10 (flip bit 1).
2
Keep a visited array so no code repeats. The walk 0 → 1 → 3 → 2 uses 4 codes, all different. Check the loop: 2 = 10 and 0 = 00 differ in one bit, so this list is valid.
3
If the walk gets stuck early, undo the last step and try the next bit. That is backtracking.
4
The loop check is needed. For n = 3, the walk 0, 1, 3, 2, 6, 4, 5, 7 uses all 8 codes and every step flips one bit, but 7 = 111 and 0 differ in three bits, so the list does not loop.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> grayCode(int n) {
        int total = 1 << n;
        vector<bool> visited(total, false);
        vector<int> path = {0};            // the walk so far, starting at code 0
        visited[0] = true;
        dfs(0, n, visited, path);
        return path;
    }

private:
    // Standing on code `cur`, try flipping each bit. Returns true when the walk has every code and loops back to 0.
    bool dfs(int cur, int n, vector<bool>& visited, vector<int>& path) {
        if ((int)path.size() == (1 << n)) {
            // The last code must be one bit away from 0, which means it is a power of two.
            return (cur & (cur - 1)) == 0;
        }
        for (int b = 0; b < n; b++) {
            int next = cur ^ (1 << b);     // flip bit b
            if (visited[next]) continue;
            visited[next] = true;
            path.push_back(next);
            if (dfs(next, n, visited, path)) return true;
            path.pop_back();               // dead end: undo this step and try the next bit
            visited[next] = false;
        }
        return false;
    }
};

Complexity

Time O(N · 2^N)Space O(2^N)

Here N is n. There are 2^N codes, and each code tries N bits, so the walk costs N · 2^N if it never gets stuck. The search does not promise that, so this is the best case. The recursion is 2^N levels deep, so this only works for small n.

Better approach

Why brute force is slow

The search has to choose a bit at every step and remember which codes it used. A dead end means undoing steps and trying again.

What repeated work are we doing?

Each step asks again which bit can flip, and checks a visited array. The rule for the whole list is never written down, so the search has to work it out again.

What information can we reuse?

The (n − 1)-bit list is already a valid Gray code. Copy it in reverse and set the top bit, and the n-bit list follows with no search and no visited array.

New approach

Idea

Build the list one bit at a time. To go from the (n − 1)-bit list to the n-bit list, copy it in reverse order, set the new top bit on every copy, and append the copies. The first half is unchanged, so its neighbours are still one bit apart. The second half is the old list reversed with one bit added, so its neighbours are one bit apart too.

Thinking process

1
A list for n bits can be built from the list for n − 1 bits, so start small.
2
n = 1: [0, 1]. For n = 2, reverse it to [1, 0] and set the top bit (value 2): [3, 2]. Append: [0, 1, 3, 2].
3
Reversing is what makes the join work. The first new code is the old last code with the top bit set. Here 1 = 01 becomes 3 = 11, and those differ in one bit.
4
Check the loop: the list ends at 2 = 10, and 2 and 0 differ in one bit.
5
Round n = 3: reverse [0, 1, 3, 2] to [2, 3, 1, 0] and add 4 to each: [6, 7, 5, 4]. The full list is [0, 1, 3, 2, 6, 7, 5, 4].

Code & Implementation

better.cpp

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> codes = {0};           // the 0-bit list: just code 0
        for (int b = 0; b < n; b++) {
            int top = 1 << b;              // the new bit for this round
            // Append the list in reverse, with the new bit set. The first copy is the old last code
            // plus top, which is one bit away from it, so the join is safe.
            for (int i = (int)codes.size() - 1; i >= 0; i--) {
                codes.push_back(codes[i] | top);
            }
        }
        return codes;
    }
};

Complexity

Time O(2^N)Space O(1)

Round b copies the 2^b codes made so far, so the rounds cost 1 + 2 + … + 2^(N−1) = 2^N − 1 in total. The list it builds is the answer, so it uses no other memory. The cost is the same as the optimal below; the difference is the idea.

Optimized approach

Idea

Start from brute force

The DFS builds the walk one flip at a time, with a visited array, and backs up when stuck. The formula removes the search completely.

Find the repeated work

Nothing is repeated once the rule is known. The brute force pays to choose and check each code. The formula gives code i straight away, from i alone.

Define the state — what variables do I need?

i: The position in the list, from 0 to 2^n − 1. It is also the plain binary number we convert.
i >> 1: i shifted right by one bit. Bit k of i >> 1 is bit k + 1 of i, so each bit is compared with the bit just above it.
code = i ^ (i >> 1): The i-th Gray code. Bit k of code is bit k of i XOR bit k + 1 of i.

Define validity

Use code(i) = i XOR (i >> 1) for every i from 0 to 2^n − 1. The codes are all different, and code(i) and code(i + 1) differ in exactly one bit, so the list is valid.

Define the transitions — when does each pointer move, and why is it safe?

For each i from 0 to 2^n − 1

output i ^ (i >> 1)

The map is one-to-one (see whyItWorks), so every value from 0 to 2^n − 1 appears exactly once.

Going from i to i + 1

nothing to track; the formula gives the next code

The two codes differ in one bit, so the step is always legal.

At the end (the wrap)

check that code(2^n − 1) = 2^(n−1)

The last code is the top bit alone, one bit away from 0, so the list loops. For n = 3: code(7) = 111 XOR 011 = 100 = 4.

What does the current window add to the answer?

Each i adds one code, and no two values of i share a code, so the list ends up with all 2^n values once each.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> grayCode(int n) {
        int total = 1 << n;
        vector<int> res;
        res.reserve(total);
        for (int i = 0; i < total; i++) {
            // The i-th Gray code: XOR i with itself shifted right by one bit.
            res.push_back(i ^ (i >> 1));
        }
        return res;
    }
};

Complexity

Time O(2^N)Space O(1)

The loop runs 2^N times, with one shift and one XOR each time. The output list has 2^N numbers, and that list is the answer, so no other memory is needed.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	From 0, flip one bit at a time, never reuse a code, back up when stuck	O(N · 2^N)	O(2^N)
Better	Start from [0]; each round, append the list in reverse with the new top bit set	O(2^N)	O(1)
Optimal	Code number i is i XOR (i shifted right by one); loop i from 0 to 2^n − 1	O(2^N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“list all numbers from 0 to 2^n − 1”The set of values is fixed, so only the order is free.
“neighbours differ in exactly one bit”Each step is a single bit flip: XOR with one power of two.
“the first and last also differ in one bit”The list must loop, so the wrap pair must be one flip apart too.

every n-bit value once+each step flips one bit+the list closes into a loop→Bitmask state — Gray code (one bit flips per step)

Here each state is a bit pattern, and every step flips exactly one bit. This is the anchor of the bitmask sub-pattern: a mask is a state you walk through. What makes this different from Counting Bits or Power of Two is that the order of the values matters, not how many bits they have. The formula works because XOR with a shifted copy turns "flip one bit at a time" into a direct rule.

Don't make this mistake

Pattern confusion: counting up in plain binary

✗ for (int i = 0; i < (1 << n); i++) res.push_back(i);

✓ for (int i = 0; i < (1 << n); i++) res.push_back(i ^ (i >> 1));

All the numbers are there, but the order breaks the rule. For n = 2 the plain list is 0, 1, 2, 3. From 1 (01) to 2 (10) flips two bits. The Gray list is 0, 1, 3, 2.

Shifting the wrong way

✗ res.push_back(i ^ (i << 1));

✓ res.push_back(i ^ (i >> 1));

For n = 2 the wrong formula gives 0, 3, 6, 5. The value 6 is outside 0 to 3, so the list is not made of the 2^n codes. The shift has to bring the bit above down, not push bits up.

Reflecting without setting the top bit

✗ codes.push_back(codes[i]);

✓ codes.push_back(codes[i] | top);

For n = 2, starting from [0, 1], the reversed copy without the top bit is [1, 0]. The list becomes [0, 1, 1, 0], which repeats 1. Setting the top bit (value 2) makes the copy [3, 2].

Stopping the DFS at 2^n codes without the loop check

✗ if ((int)path.size() == (1 << n)) return true;

✓ if ((int)path.size() == (1 << n)) return (cur & (cur - 1)) == 0;

For n = 3 the walk 0, 1, 3, 2, 6, 4, 5, 7 uses all 8 codes and flips one bit at each step, but 7 = 111 and 0 differ in three bits. The loop rule is part of the problem, so the last check is needed.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture