Here is my solution with O(k) space.


  • 1
    N

    The idea is:
    Use only one array or array list with space of rowIndex + 1, fill them all with 1. Then loop from 2 to rowIndex, calculate from end back to middle (half), mirror it to first half. And we can reuse same array to calculate next row since the calculation will use (current position) and (current position - 1) data.

    public class Solution {
    public ArrayList<Integer> getRow(int rowIndex) {
        if (rowIndex < 0) {
            return null;
        }
        ArrayList<Integer> data = new ArrayList<>(rowIndex + 1);
        for (int i = 0; i < rowIndex + 1; i ++) {
            data.add(1);
        }
        if (rowIndex < 2) {
            return data;
        }
        for (int i = 2; i <= rowIndex; i ++) {
            fillpt(data, i);
        }
        return data;
    }
    
    private void fillpt(ArrayList<Integer> data, int row) {
    	int half = row - (row / 2);
    	for (int i = row - 1; i >= half; i--) {
    		data.set(i, data.get(i) + data.get(i - 1));
    	}
    	for (int i = row - 1; i >= half; i --) {
    		data.set(row - i, data.get(i));
    	}
    }

  • 0
    C
    class Solution:
    # @return a list of integers
    def getRow(self, rowIndex):
    	
    	res = [1]
    
    	for i in range(1,rowIndex+1):
    		res.append(1)
    		for j in range(1,i)[::-1]:
    			res[j] = res[j]+res[j-1]
    
    	return res
    

  • 1
    F
    class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> row(1, 1);                      // start with row with 1 value of [1] i.e 0th rowIndex 
            for (int i = 0; i < rowIndex; ++i) {        // for rowIndex number of times  [i.e. to get rowIndexth row]
               row.emplace(row.begin(), 1);             //     prepend 1 to previous calculated row at the beginning
               for (int k = 1; k < row.size() - 1; ++k) //     for each element in the newly updated row except first & last 
                   row[k] += row[k+1];                  //         calculate each row element by defn of pascal triangle 
            }
            return row;                                 // return the calculted row for rowIndx
        }
    };
    
    Example Walkthroughs: 
    
        1] r = 0, row = [1], return row
        2] r = 3, row = [1]
             i = 0 < r, row = [1, 1]
             i = 1 < r, row = [1, 1, 1]
                  k E [1, 2), row [k] = row[k] + row[k+ 1]  =>  row = [1, 2, 1]
             i = 2 < r, row = [1, 1, 2, 1]
                  k E [1, 3), row [k] = row[k] + row[k+ 1]  =>  row = [1, 3, 3, 1]
             i = 3, return row => [1, 3, 3, 1]
    
    

  • 0
    S

    Hi @CCLeaves, Thanks for your post. Even though your code is elegant, it still would be better to word your idea. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    S

    Hi @Functor, Thanks for your post. Even though your code is elegant, it still would be better to word your idea. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    F

    Updated with explanation, hope that helps.


Log in to reply
 

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