:orphan:

Pascals Triangle
================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/pascals-triangle/

Given an integer ``numRows``, return the first numRows of **Pascal's
triangle**.

In **Pascal's triangle**, each number is the sum of the two numbers
directly above it as shown:

|image1|

 

**Example 1:**

::

   Input: numRows = 5
   Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

**Example 2:**

::

   Input: numRows = 1
   Output: [[1]]

 

**Constraints:**

- ``1 <= numRows <= 30``

.. |image1| image:: https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif

.. highlight:: python

Pattern
-------
Array, Dynamic Programming

Solution
--------
Right align the normal presentation of Pascal's Triangle. ::

        1        1
       1 1       1 1
      1 2 1  --> 1 2 1
     1 3 3 1     1 3 3 1
    1 4 6 4 1    1 4 6 4 1

Observe that a middle entry is the sum of the entry directly above and to the
north-west. The first/last entry is always 1.

Code
----

.. literalinclude:: ../problems/easy/pascals-triangle/pascals_triangle__approach_1.py
    :language: python
    :lines: 9-

Test
----
>>> from pascals_triangle__approach_1 import generate
>>> generate(3)
[[1], [1, 1], [1, 2, 1]]
>>> generate(6)
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]

Complexity
----------
| :math:`n` is the number of rows in the triangle
| Time: :math:`O(n^2)` — triangle is half of a square of side :math:`n`
| Auxiliary Space: :math:`O(1)`

.. autofunction:: pascals_triangle__approach_1.generate