Java Concise 10-Line Simple Solution


  • 0
    M
    public List<Integer> grayCode(int n) {
    
    		List<Integer> ans = new LinkedList<Integer>();
    
    		if (n == 0) {
    			ans.add(0);
    			return ans;
    		}
    		
    		List<Integer> previous = grayCode(n - 1);
    
    		int factor = 1 << (n - 1);
    
    		for (int num : previous) {
    			ans.add(ans.size() / 2, num);
    			ans.add(1 + ans.size() / 2, num + factor);
    		}
    		return ans;
    	}

  • 0
    T

    Complexity explodes: adding an item to a linked list at position i is a linear operation, same with array list. Linked list needs to find ith link node inside which takes i steps, array list would find it immediately, but inserting needs to move n-i elements.

    This means that the for loop is O(n^2), right? I think if you iterate twice, copying the previous result and then copying the result in reverse and adding factor would reduce it to 2n. You can even use the same list if you save the size before iterations and only copy that many elements.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.