89. Gray Code

Link

key ideas

• Create an array res with size 2^n

• Set res[0] = 0 as the base case

• Iterate over the array, trying to insert a valid number in every iteration.

• To find a valid number, we create another loop, and in this nested loop:

  • toggle the rightmost bit and check if the new number is in res already (use a hashtable to make the lookup O(1))

    • if the new number is in res already, we shift the bit on the left side of the current bit.

    • if it is not in res yet, we add the new number to res and stop the current bit shift iteration, getting into the i + 1 iteration

  • Because we always start bit-shifting from the rightmost bit, the last number will always be the number whose leftmost bit is 1 and every other bit is 0 (10, 100, etc), which automatically differs from the 1st number(0, we start from res[0] = 0) by 1 bit

def grayCode(self, n: int) -> List[int]:
    res = [0] * 2 ** n
    t = {0: False}
    for i in range(1, len(res)):
        num = res[i - 1]
        for b in range(n):
            next_num = num ^ 1 << b
            if t.get(next_num, True):
                res[i] = next_num
                t[next_num] = False
                break
    return res

Time complexity:

we iterate over res, whose size is 2^n, and in each iteration, we shift n bits in the worst case, so O(n * 2^n)

Space complexity:

O(2^n) - res's size is 2^n