# 99 Scala Problems 03 - Find the Kth element of a list

## The problem

**P03** (*) Find the Kth element of a list.
By convention, the first element in the list is element 0.

Example:

```
scala> nth(2, List(1, 1, 2, 3, 5, 8))
res0: Int = 2
```

## Initial thoughts

I expect the solution to be trivial using the indexing capabilities of `List`

types, such as in any language that supports indexed lists. The functional solution cannot use indexing and shall reduce the list element by element.

## The procedural solution

```
def findKth[A](k:Int, l:List[A]):A = {
if (k >= 0 && k < l.length) l(k)
else throw new NoSuchElementException
}
```

Since indexing out of bounds (in both directions) throws `IndexOutOfBoundsException`

we first check if the index is safe. The logical AND operation is expressed in Scala by `&&`

.

Knowing that a wrong indexing throws an exception we could also catch it and throw the 'right' one. This results in

```
def findKth[A](k:Int, l:List[A]):A = {
try l(k)
catch {
case e:IndexOutOfBoundsException => throw new NoSuchElementException
}
}
```

which probably states more clearly that the main job of the function is to replace one exception with another one.

## The recursive solution

A recursive solution is pretty straightforward. We just repeatedly remove the first element until and decrease the given index until it reaches 0. Using a couple of methods from the `List`

type the solution is

```
def findKth[A](k:Int, l:List[A]):A = k match {
case 0 => l.head
case k if k > 0 => findKth(k - 1, l.tail)
case _ => throw new NoSuchElementException
}
```

If however we try to avoid the use of methods, just to see if we may solve it with a pure recursive approach, we need to match two things together, which leads to

```
def findKth[A](k:Int, l:List[A]):A = (k,l) match {
case (0, h::_) => h
case (k, _::tail) if k > 0 => findKth(k - 1, tail)
case _ => throw new NoSuchElementException
}
```

The "new" thing here is that we are pattern matching a tuple of values (which is, after all, one value of a given type). Moreover, Scala pattern matching shows us another strength point in that it can match a case and simultaneously operate on the variables (in this case splitting the list).

The first case is the exit case, where the counter reached 0 and the list has an head to return, which is the nth element. Otherwise the first element of the list is removed and the function called with a decremented index. The last line covers the empty list case.

## Final considerations

The procedural approach made me learn how to **catch exceptions** in Scala and how to perform **logical comparisons**. The recursive solution taught me **pattern matching of multiple values**.

## Feedback

Feel free to use the blog Google+ page to comment the post. The GitHub issues page is the best place to submit corrections.

## Part 3 of the "99 Scala Problems" series

##### Previous articles

- 99 Scala Problems 01 - Find the last element of a list
- 99 Scala Problems 02 - Find the last but one element of a list

##### Next articles

- 99 Scala Problems 04 - Find the number of elements of a list
- 99 Scala Problems 05 - Reverse a list
- 99 Scala Problems 06 - Find out whether a list is a palindrome
- 99 Scala Problems 07 - Flatten a nested list structure
- 99 Scala Problems 08 - Eliminate consecutive duplicates of list elements
- 99 Scala Problems 09 - Pack consecutive duplicates of list elements into sublists
- 99 Scala Problems 10 - Run-length encoding of a list.
- 99 Scala Problems 11 - Modified run-length encoding
- 99 Scala Problems 12 - Decode a run-length encoded list
- 99 Scala Problems 13 - Run-length encoding of a list (direct solution)
- 99 Scala Problems 14 - Duplicate the elements of a list
- 99 Scala Problems 15 - Duplicate the elements of a list a given number of times
- 99 Scala Problems 16-20