LeetCode 89: Gray Code Solution

Problem Explanation

Explanation

To generate a valid n-bit gray code sequence, we can use a backtracking approach. The key idea is to start with 0, then recursively build the sequence by flipping a single bit at a time to create the next number in the sequence. This ensures that adjacent numbers only differ by one bit.

The algorithm follows these steps:

Start with the initial number 0.
Generate the next number by flipping a single bit at a time.
Keep track of visited numbers to avoid duplicates.
Repeat until all possible numbers have been visited.

The time complexity of this approach is O(2^n) since there are 2^n numbers in a valid gray code sequence. The space complexity is O(2^n) to store the result.

Solution Code

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0);
        for (int i = 0; i < n; i++) {
            int size = result.size();
            for (int j = size - 1; j >= 0; j--) {
                result.add(result.get(j) | (1 << i));
            }
        }
        return result;
    }
}

Frequently Asked Questions

How to solve LeetCode 89 (Gray Code)?

This page provides optimized solutions for LeetCode problem 89 (Gray Code) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 89 (Gray Code)?

The time complexity for LeetCode 89 (Gray Code) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 89 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 89 in Java, C++, or Python.