Leetcode #0119. How create formula for O(N) solution

Two days ago I tried to solve again leetcode problem 0119 Pascal’s triangle using the math approach. It is the fastest approach to calculate row in Pascal’s triangle, but… I can’t understand how it works and how to remember the formulas.

So, let’s begin from the base.

In leetcode problem number 119 Pascal’s Triangle II you need to calculate the row of Pascal’s triangle by its rowIndex.

What is Pascal’s triangle? Pascal’s triangle is a triangular array constructed by summing adjacent elements in preceding rows.

So, the simplest way to calculate this row — is to calculate step by step each row from the beginning of the triable. Just sum adjacent cells in the loop from 1 to rowIndex and return the last row as result.

public IList<int> GetRow(int rowIndex)
{
    var result = new List<int>() { 1 };
    
    if (rowIndex == 0)
        return result;

    for (int i = 1; i <= rowIndex; i++)
    {
        var row = new List<int>();
        row.Add(1);

        for (int j = 0; j < result.Count - 1; j++)
        {
            row.Add(result[j] + result[j + 1]);
        }

        row.Add(1);

        result = row;
    }

    return result;
}

Pretty easy, really?

The time complexity for such an approach is O(n²) (square time) because you have two loops: outer and inner. And total complexity calculates as multiplication n to n, where n is rowIndex. (Here is a good explanation for a similar task at StackOverflow: Time complexity of nested for-loop.)

But also the solution with linear time exists:

public IList<int> GetRow(int rowIndex)
{
    var row = new List<int>(Math.Max(rowIndex + 1, 1));

    row.Add(1);

    // first element is 1, next = prev * (n-k) / (k+1)
    for (int i = 0; i < rowIndex; i++)
    {
        // int overflow may happen
        long x = rowIndex - i;

        row.Add((int)(row[i] * x / (i + 1)));
    }

    return row;
}

I’ve checked it by all leetcode tests and it really works fine. Also, it looks very neat and concise. But how the author becomes that formula? And how to get it from the scratch, without remembering?

Here’s a simple explanation. You need also to learn some more from math to get the idea.

Pascal’s triangle is also the triangle of binomial coefficients: the bottom index is the same as the rowIndex and the upper index is 0, 1, 2, and so on. For the last element, the number is also the same as the row’s number. Here is an illustration:

triangle of binomial coefficient

Each element (n, k) can be calculated using classic factorial formula:

factorial formula for binomial coefficient

So, any random element can be calculated using that formula, but stop! You don’t need to calculate factorials, it’s really enough to multiply the previous element by this fraction. How could you get the formula for this fraction?

Just divide any next element for the previous:

So, it’s the same formula for next element if we know previous. It’s without factorials, no costly calculations, pretty and concise.

So, next time you can get this formula knowing only factorial formula.

I expect that you already seen factorial formula, because it has strong connection with very important topic in combinatorics: combinations and permutations.