Scale Engineer

Gray Code

Med
#0089Time: O(n * 2^n)Space: O(2^n)3 companies
Patterns
MathBacktrackingBit Manipulation
Companies
AmazonBloombergGoogle

Prompt

An n-bit gray code sequence is a sequence of 2n integers where:

  • Every integer is in the inclusive range [0, 2n - 1],
  • The first integer is 0,
  • An integer appears no more than once in the sequence,
  • The binary representation of every pair of adjacent integers differs by exactly one bit, and
  • The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

 

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

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

 

Constraints:

  • 1 <= n <= 16

Approaches

3 approaches with complexity analysis and trade-offs.

This approach treats the problem as a graph traversal problem. We can think of the numbers from 0 to 2^n - 1 as nodes in a graph. An edge connects two nodes if their binary representations differ by exactly one bit. The goal is to find a path that starts at 0 and visits every single node exactly once (a Hamiltonian path). A Depth First Search (DFS) with backtracking is a natural way to explore such paths.

Algorithm

  • Model the problem as finding a Hamiltonian path in a graph where vertices are numbers 0 to 2^n - 1 and an edge exists if two numbers differ by one bit.
  • Use Depth First Search (DFS) to find a path that visits every vertex exactly once.
  • Start the search from 0.
  • Maintain a visited array to avoid cycles and redundant computations.
  • A recursive function backtrack() attempts to extend the current path:
    1. Base Case: If the path length is 2^n, a solution is found. Return true.
    2. Recursive Step: Get the last number in the path, current.
    3. Iterate through all n possible bit flips of current to find potential next numbers.
    4. If a next number has not been visited:
      • Add it to the path and mark it as visited.
      • Recursively call backtrack().
      • If the recursive call returns true, propagate true up the call stack.
      • If it returns false, backtrack by removing next from the path and unmarking it as visited.
    5. If all neighbors have been explored without finding a complete path, return false.

Walkthrough

We start with a path containing only 0. We then recursively try to extend this path. At each step, we look at the last number added to our path and try to find a valid next number. A valid next number is one that differs by only one bit from the current number and has not been visited yet. We can find potential next numbers by flipping each of the n bits of the current number one at a time. If we find an unvisited valid neighbor, we add it to our path and recurse. If the recursive call eventually leads to a full path of length 2^n, we have found our solution. If we hit a dead end (a number from which all valid neighbors have already been visited, but the path is not yet complete), we backtrack by removing the last number from the path and trying a different neighbor.

class Solution {    List<Integer> result;    boolean[] visited;    int n;     public List<Integer> grayCode(int n) {        this.n = n;        result = new ArrayList<>();        // Total numbers are 2^n        int totalNumbers = 1 << n;        visited = new boolean[totalNumbers];                result.add(0);        visited[0] = true;                backtrack();        return result;    }     private boolean backtrack() {        if (result.size() == (1 << n)) {            return true;        }         int current = result.get(result.size() - 1);        for (int i = 0; i < n; i++) {            int next = current ^ (1 << i);            if (!visited[next]) {                visited[next] = true;                result.add(next);                if (backtrack()) {                    return true;                }                // Backtrack                result.remove(result.size() - 1);                visited[next] = false;            }        }        return false;    }}

Complexity

Time

O(n * 2^n)

Space

O(2^n)

Trade-offs

Pros

  • It is a general approach that can find any valid Gray code sequence, not just a specific one.

  • The logic directly follows the definition of the problem, making it conceptually straightforward.

Cons

  • Significantly less efficient than other approaches with a time complexity of O(n * 2^n).

  • The overhead of recursion and state management (the visited array and the result list) makes it slower in practice.

Solutions

int gray ( x ) { return x ^ ( x >> 1 ); }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem