This is our solution and implementation to problem #89: Gray Code on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy our video which outlines our analysis and implementation approach, a breakdown on the space and time complexity, and the full code implementation.
Note: the code and contents here might be slightly different than what is in the video. We've made some improvements to some of the code since recording.
If you would like to view the original problem and solve it, please visit: Gray Code on LeetCode.
Problem Analysis
The problem asks us to return a list of integers, in base 10, where the same numbers in binary (base 2) have one and only one of its digits differ between its previous and next entry, and the first and last entries must also only differ by one digit. The problem also outlines additional constraints that the first integer must be 0 and that no integer appears more than once. The fixed starting point of 0 allows us to do some analysis on what the second digit, and last digit, must be. Note that the nature of the list of numbers implies a symmetry: the 2nd and last items will have the same possibilities, the 3rd and 2nd to last items will have the same possibilities, etc. The table below oulines different possible values for the 2nd and last positions for different values of n:
n | binary options | decimal options |
---|---|---|
2 | 01, 10 | 1, 2 |
3 | 001, 010, 100 | 1, 2, 4 |
4 | 0001, 0010, 0100, 1000 | 1, 2, 4, 8 |
5 | 00001, 00010, 00100, 01000, 10000 | 1, 2, 4, 8, 16 |
We can see a clear pattern emerging: the 2nd number, and last number, both must be powers of 2. Let's do a similar analysis for the 3rd, and 2nd to last positions:
n | binary options | decimal options |
---|---|---|
2 | 11 | 3 |
3 | 011, 101, 110 | 3, 5, 6 |
4 | 0011, 0101, 0110, 1001, 1010, 1100 | 3, 5, 6, 9, 10, 12 |
In this second table, it may be possible to derive a statement such as "all numbers are of the form 2^n +- c", but it will be simpler to consider it as all numbers which have an even number of "1" digits in its binary form. Similarly, in the first table, all binary numbers have an odd number of "1" digits. This means that the list we will be returning will have values [bE, bO, bE, bO, ...., bE]. This implies that the size of the list being returned by the solution must be a multiple of 2 to preserve the alternation. Furthermore, each position p (zero indexed) must have exactly Min(p, len-p) digit alterations from 0: [0, 1, 2, .... len/2 ...., 2, 1]. The length of the list will be 2^n, as each integer must appear exactly one.
With the information above, we are close to understanding how to generate the sequence. The diagram below outlines:
- A binary tree representing different binary numbers where n is 3, drawn in black marker.
- An example sequence for n = 3, drawn in blue marker at the bottom just above the final text.
- The example sequence in decimal form, drawn in green marker just above the binary version.
- The order of sequence items of each leaf node, with arrows indicating if the direction is reversed, drawn in purple marker.
- The correct order, if the items in purple are swapped, drawn in blue marker.
In other words, we've drawn the original tree, then have analyzed how we can swap certain nodes to allow the leaf nodes to appear in an order which will satisfy the constraints of the problem. We've determined the rules for swapping are:
- Each right child should have its children swapped.
- Each left child should have its children in the normal order.
Implementation Strategy
In this implementation, we will take advantage of some of the properties discussed above. The way subtrees are swapped, we can see that a pattern emerges: for each leaf at position p with value V(p) starting with position 0:
- If p/2 is odd: V(p) = p•2.
- If p/2 is even: V(p) = p•2+1
With this in mind, we can take a purely iterative approach to construct the list, and we will not need to initialize the list beforehand, we can add elements as we go. In our approach, we will perform an iteration for a total of 2^(n-1) times, and each iteration will add two items to the list.
Space and Time Complexity
If we include the return value in the space complexity, it will be O(2^n) which is the size of the return element itself. If we exclude from the analysis, it will be O(1), as only constant auxiliary space is used. The time complexity is O(2^(n-1)), as we will be performing an iteration of that many steps.
Additional Resources
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.