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

Published

## 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

``````assert(nextRow(List(1, 1)) == List(1, 2, 1))
assert(pascalsTriangle(0) == List(1))
assert(pascalsTriangle(1) == List(1, 1))
assert(pascalsTriangle(2) == List(1, 2, 1))
assert(pascalsTriangle(3) == List(1, 3, 3, 1))
assert(pascalsTriangle(4) == List(1, 4, 6, 4, 1))
``````

## 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

1. ### 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').

2. ### Pattern Matching

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

``````assert("Hello World".collect {
case character if Character.isUpperCase(character) => character.toLower
} == "hw")
``````
3. ### 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.

``````assert(List(1, 2, 3).zip(List(5, 6, 7)) == List(1 -> 5, 2 -> 6, 3 -> 7))

assert(List(1, 2).zip(List(5, 6, 7)) == List(1 -> 5, 2 -> 6))

assert(List(5, 6).zipWithIndex == List(5 -> 0, 6 -> 1))

assert(List(5, 6).zipAll(List('A'), 9, 'Z') == List(5 -> 'A', 6 -> 'Z'))

assert(List(5).zipAll(List('A', 'B'), 1, 'Z') == List(5 -> 'A', 1 -> 'B'))
``````

# Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

## How our 100 algorithms look

1. A description/goal of the algorithm.
2. An explanation with both Scala and logical parts.
3. A proof or a derivation, where appropriate.
4. Links to Scala concepts used in this specific algorithm, also unit-tested.
5. An implementation in pure-functional immutable Scala, with efficiency in mind (for most algorithms, this is for paid subscribers only).
6. Unit tests, with a button to run them immediately in our in-browser IDE.

### Study our 100 Scala Algorithms: 6 fully free, 100 published & 0 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

### Explore the 22 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

## Subscribe to Scala Algorithms

Maximize your Scala with disciplined and consistently unit-tested solutions to 100+ algorithms.

Use it from improving your day-to-day data structures and Scala; all the way to interviewing.