119. Pascal's Triangle II

Problem¶

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it

Example 1:

Input: rowIndex = 3
Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

Input: rowIndex = 1
Output: [1,1]

Constraints:

• 0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

Solve¶

White board¶

Analyzing the problem¶

It nice to have some follow up, so I decided to go up with that route directy

The problem have quote directly that

(0-indexed) row of the Pascal’s triangle.

• This mean, we have 0 -> [1] and 1 -> [1,1] as a base value
• I overlook about this so it take me some time to realized, mostly because of why my result return to [1,2,1] instead of [1,3,3,1] with row index 3.
• There is a lot of Off by one error to be consider like:
  • We need to start calculating at row 2
  • The calculating need to add 1 to the last number every time process to the next row.

Ideal¶

Now let talk about the main function solved the problem

• Let say I have a full int[rowIndex] array to work at
• Start at 2 (0 and 1 index is base level)
• A triangle calculating formula is that: With row index i (i>=2), it always have

row[i].length = i + 1 //0 indexed, remember off by one error
row[i, 0]     = 1 //First element
row[i, i + 1] = 1 //Last element

// For all other element
row[i, j] = row[i-1, j] + row[i-1, j-1] 

So the ideal is that we update the row to the next one directly using above info with out the need to create a new array.

By the define, a array that being used for storing result shouldn’t being count for space complexity. But let say we only have a single array to work with here.

Also O(rowIndex) extra space, mean we can still make 2 array with rowIndex length.

To do that, I need see that: row[i-1, j] is update to row[i, j] by adding row[i-1, j-1]. We overwrite the value of our row value, so that:

row[i, j] = row[i-1, j] + row[i-1, j-1]

become in-depended with i, making it:

row[j]    = row[j] + row[j - 1]

Let enforce a rule that we update from left to right. So j value running from 1, 2, 3, ... so on till current row length.
We could see this isn’t work, as we update the value of row[j], the next time we need to access it previous value to calculating row[j+1] = row[j+1] + row[j].

So we need to have a temporary variable to storing the previous value of row[j] before overwriting it.

Quick implementation¶

With that much information, i directly try to implementation in python.

Which is accepted with

Runtime 44 ms, Beats 18.96%
Memory 16.2 MB, Beats 53.14%

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = [1,1]
        if (rowIndex == 0):
            return [1]
        if (rowIndex == 1):
            return [1,1]
        for row in range(2,rowIndex+1):
            memo = res[0]
            for i in range(1,row):
                memo, res[i] = res[i], res[i] + memo
            res.append(1)
        return res

• We not have to go for a fix size array just yet, just to implement the process of update res array using our formula.
• memo is used to store the previous value of res[i], while res[i] is overwritten by the value of res[i] + memo = res[i] + res[i-1]

C Implementation¶

c
O(n ** 2)

C is a language that I can have better control on the program memory, so I choosing it to finish the problem. Not thing to fancy, i try to implementing the python code exactly.

But I do run into some Segfault because of 0-index causing Off by one error, cost me some time to debug and rewriting the code.

The final implementation is here:

Which is accepted with

Runtime 3 ms, Beats 51.12%
Memory 6.4 MB, Beats 38.98%

/**

 * Note: The returned array must be malloced, assume caller calls free().
 */
int* getRow(int rowIndex, int* returnSize){
    *returnSize = rowIndex + 1;
    int* res = malloc(sizeof (int) * *returnSize);
    res[0] = 1;
    if (rowIndex == 0) return res;

    res[1] = 1;
    for (int currRow = 2; currRow <= rowIndex; currRow ++){
        int memo = res[0];
        int temp = 0; 
        for (int i = 1; i < currRow; i ++){
            temp = memo;
            memo = res[i];
            res[i] = res[i] + temp;
        }
        res[currRow] = 1;
    }
    return res;
}

I try to do some more fancy by pushing all of the variable definition to the top of the function, while it doesn’t help anything with the memory, but at least i get 0 ms runtime (Beats 100.00%of users with C!!!). But this is base purely on the load of Leetcode, so it quite random/unreliable on this runtime result.

I do look at some answer of other user using Leetcode interface with 0ms run, or lower memory. They doesn’t making any difference from my code (other than having different variable name), which just mean that Leetcode result is unreliable.

Yanked code

int* getRow(int rowIndex, int* returnSize){
    int size = rowIndex + 1;
    int *output = malloc(size * sizeof(int));
    output[0] = 1;
    int a = 0, b = 1;
    for(int i = 0; i <= rowIndex; i++){
        a = 0, b = 1;
        for(int j = 0; j < i; j++){
            output[j] = a + b;
            a = b;
            b = output[j+1];
        }
        output[i] = 1;
    }
    *returnSize = size;
    return output;
    free(output);
}