<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Pascal's Triangle
Step1:  Naive Solution
Given a piece of paper and 10 minutes this was the naive solution I could come up with, however it is horribly inefficient calculating all previous rows in order to get the current row. The time complexity is O((n² + n)/2) and space complexity is O(2n). However it does give the expected output.
Step2:  Optimised Solution
However it is possible to do this in O(n) space and O(n/2) time complexity
Step3:  Corner Cases
There are a number of corner cases which should be considered, for example passing in a negative integer, or passing a string for example, but the typical corner case with pascals triangle is an integer overflow when dealing with large numbers. In python however integers have arbitrary size, and expand as required, for example
Step4:  With very large numbers in a python solution you will eventually run out of memory, for example
<ASSISTANT_TASK:>
Python Code:
import sys; sys.path.append('../..')
from puzzles import leet_puzzle
leet_puzzle('pascals-triangle')
Explanation: Pascal's Triangle
End of explanation
def pascals_triangle(k):
    prev_row = None
    for r in xrange(k+1):
        row = [None] * r
        for c in xrange(r):
            if c == 0 or c == r-1:
                row[c] = 1
            else:
                row[c] = prev_row[c] + prev_row[c-1]
        prev_row = row
    return row
for k in xrange(1, 10):
    print pascals_triangle(k)
%%timeit
pascals_triangle(40)
Explanation: Naive Solution
Given a piece of paper and 10 minutes this was the naive solution I could come up with, however it is horribly inefficient calculating all previous rows in order to get the current row. The time complexity is O((n² + n)/2) and space complexity is O(2n). However it does give the expected output.
End of explanation
def pascals_triangle_2(k):
    
    k = k - 1
    
    row = [1]
    
    # only need to calculate half of the row, since the triangle is
    # symmetric
    for n in xrange(k / 2):
        row.append(row[n] * (k - n) / (n + 1))
        
    # middle element is repeated only for odd values of k
    r = list(reversed(row))
    r = r[1:] if k % 2 == 0 else r
    
    return row + r
for k in xrange(1, 10):
    print pascals_triangle_2(k)
%%timeit
pascals_triangle_2(40)
Explanation: Optimised Solution
However it is possible to do this in O(n) space and O(n/2) time complexity:
End of explanation
pascals_triangle_2(50)
Explanation: Corner Cases
There are a number of corner cases which should be considered, for example passing in a negative integer, or passing a string for example, but the typical corner case with pascals triangle is an integer overflow when dealing with large numbers. In python however integers have arbitrary size, and expand as required, for example:
End of explanation
import sys
result2 = pascals_triangle_2(sys.maxint - 1)
Explanation: With very large numbers in a python solution you will eventually run out of memory, for example:
End of explanation
<END_TASK>