How do you approach Gray Code?

The i-th reflected gray code is i XOR (i >> 1).

What are common mistakes on Gray Code?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

Sitelet https://gitgood.dev/coding/gray-code

gitGood.dev

← Back to problems

Gray Code

MediumAlgorithms

Description

An n-bit gray code sequence is a list of 2ⁿ integers where every value is in [0, 2ⁿ - 1], the first value is 0, every value appears once, and adjacent values (including the first and last) differ by exactly one bit.

Return any valid n-bit gray code sequence using the standard reflected-binary construction.

Example 1

Input: n = 2

Output: [0,1,3,2]

Explanation: 00 -> 01 -> 11 -> 10, each step flips one bit.

Constraints

- 1 <= n <= 16

Gray Code: approach, complexity and pitfalls

A medium backtracking problem, graded against 6 test cases (4 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

If you are stuck

Show the 2-step hint ladder

The i-th reflected gray code is i XOR (i >> 1).
Generate it directly for i from 0 to 2ⁿ - 1.

The optimal approach

Show the approach: The approach

Direct formula. The reflected binary gray code maps index `i` to `i ^ (i >> 1)`. Emitting this for `i = 0..2ⁿ-1` yields a valid sequence where consecutive entries differ by one bit.

Time: O(2ⁿ). Space: O(2ⁿ) for the output.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.