# Scala algorithm: Find the contiguous slice with the minimum average

Published

## Algorithm goal

In an array, find the contiguous slice that has the minimum average.

For example, \([3, 1, 9, 1, 2]\) has slices:

- \([3, 1]\), average \(2\).
- \([3, 1, 9]\), average \(4.33\).
- \([3, 1, 9, 1]\), average \(3.5\).
- \([3, 1, 9, 1, 2]\), average \(3.2\).
- \([1, 9]\), average \(5\).
- \([1, 9, 1]\), average \(3.67\).
- \([1, 9, 1, 2]\), average \(3.25\).
- \([9, 1]\), average \(5\).
- \([9, 1, 2]\), average \(4\).
- \([1, 2]\), average \(1.5\).

The slice with the minimum average is \([1, 2]\) because it has minimum average of \(1.5\).

This is similar to Codility's MinAvgTwoSlice problem.

## Test cases in Scala

```
assert(findMinAvgSlice() == None)
assert(findMinAvgSlice(1) == None)
assert(findMinAvgSlice(1, 2) == Some(SubSlice(startIndex = 0, List(1, 2))))
assert(
findMinAvgSlice(3, 1, 2) == Some(SubSlice(startIndex = 1, List(1, 2)))
)
assert(
findMinAvgSlice(3, 1, 1, 2) == Some(SubSlice(startIndex = 1, List(1, 1)))
)
assert(
findMinAvgSlice(3, 1, 2, 1, 2) ==
Some(SubSlice(startIndex = 1, List(1, 2, 1)))
)
assert(
findMinAvgSlice(3, 1, 9, 1, 2) ==
Some(SubSlice(startIndex = 3, List(1, 2)))
)
assert(
findMinAvgSlice(Int.MaxValue, Int.MaxValue, 1, 2) ==
Some(SubSlice(startIndex = 2, List(1, 2)))
)
assert(
findMinAvgSlice(3, 4, Int.MinValue, Int.MinValue, 1, 2) ==
Some(SubSlice(startIndex = 2, List(Int.MinValue, Int.MinValue)))
)
```

## Algorithm in Scala

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

## Explanation

We could find the solution using a brute-force search which would be computationally expensive because it means for every starting element, we have to consider nearly N other elements, so our complexity would be at least \(O(n^2)\).

However, this (and similar problems like MaximumProfitStockPrices), are often mathematical in nature, and it is wise to have some mathematics in your toolbox to find a more optimal algorithm, which you will find here: (this is Â© from www.scala-algorithms.com)

### Mathematics

Suppose \(V(p, l)\) is the average of \(l\) numbers starting at position \(p\). For example, \(V(3, 2)\) is \((A_3 + A_4) \div 2\), where \(A_i\) is the \(i\)th element of the input array.

Consider that a slice is of minimum length 2. If the next number decreases our average, then we get a slice of length \(3\).

However, if we extend it by 2, and it decreases our average, we get the following equation:

\(V(p, 4) < V(p, 2) \implies 2 (A_p + A_{p+1} + A_{p+2} + A_{p+3}) < 4(A_p + A_{p+1})\).

\(\implies 2(A_{p+2} + A_{p+3}) < 2(A_p + A_{p+1})\), which would mean that we have just found a new and smaller slice of size 2.

## Scala concepts & Hints

### Collect

'collect' allows you to use Pattern Matching, to filter and map items.

### Drop, Take, dropRight, takeRight

Scala's `drop` and `take` methods typically remove or select `n` items from a collection.

### Option Type

The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!

### Pattern Matching

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

### Sliding / Sliding Window

Get fixed-length sliding sub-sequences (sliding windows) from another sequence

### View

The

`.view`

syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.