Pascal's Triangle II JAVA using O(k) extra space


  • 0
    S
        public List<Integer> getRow(int rowIndex) {
        
    	int k = 0;
    	List<Integer> row = new ArrayList<Integer>();
    	
    	int temp1 = 1, temp2 = 1;
    	
    	while (k <= rowIndex) {
    		
    		if (k == 0) {
    			row.add(1);
    			++k;
    			continue;
    		}
    		
    		if (k == 1) {
    			row.add(1);
    			++k;
    			continue;
    		}
    
    		for (int i = 1; i < k; ++i) {
    			if (i == 1) temp1 = row.get(i - 1) + row.get(i);
    			else if (i == 2) temp2 = row.get(i - 1) + row.get(i);
    			else if (i % 2 != 0) {
    				row.set(i - 2, temp1);
    				temp1 = row.get(i - 1) + row.get(i);
    			}
    			else {
    				row.set(i - 2, temp2);
    				temp2 = row.get(i - 1) + row.get(i);
    			}
    		}
    		
        	if (k >= 2) {
        		int i = k - 1;
        		if (i % 2 == 0) {
        			row.set(i, temp2);
        			row.set(i - 1, temp1);
        		}
        		else {
        			row.set(i, temp1);
        			row.set(i - 1, temp2);
        		}
        	}
    
    		row.add(1);
    
    		++k;
    	}
    
    	return row;
    	
    }
    

    Use 2 integers to store the sums of the two numbers of previous rows. Rotate and replace the previous row of numbers to get the new row of numbers.


  • 0
    S

    Actually when I re-think about it, this algorithm only used O(1) extra space, not O(k), sorry.


Log in to reply
 

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