# Scala algorithm: Compute nth row of Pascal's triangle

Published , last updated

## Algorithm goal

In a Pascal's triangle, a number in a row is created by adding the two numbers directly above it; the first row is contains only 1, and the second row contains 1 and another 1.

This is a Pascal's triangle to its 5th row:

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1

The goal is to compute the nth row of the triangle.

## Test cases in Scala

## Algorithm in Scala

8 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!

## Explanation

Breaking down the problem to its constituent part, we need to compute the next row from a previous row. Noticing the fact that the next row's items are really a sum of pairs of previous row's items, combined with previous row's items slightly shifted, notice that to go from row [1,2,1], we produce a new row which is [1, 2 + 1, 1 + 2, 1], which is [0 + 1, 1 + 2, 2 + 1, 1 + 0], which is [0, 1, 2, 1] + [ 1, 2, 1, 0 ].

Effectively, we just need to sum the original row with the original row slightly shifted (0 added). (this is Â© from www.scala-algorithms.com)

## Scala concepts & Hints

### Lazy List

The 'LazyList' type (previously known as 'Stream' in Scala) is used to describe a potentially infinite list that evaluates only when necessary ('lazily').

### Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

### Zip

'zip' allows you to combine two lists pair-wise (meaning turn a pair of lists, into a list of pairs)

It can be used over Arrays, Lists, Views, Iterators and other collections.