# Find the contiguous slice with the minimum average

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

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

`assert("Hello World".collect { case character if Character.isUpperCase(character) => character.toLower } == "hw")`

- Drop, Take, dropRight, takeRight
Scala's `drop` and `take` methods typically remove or select `n` items from a collection.

`assert(List(1, 2, 3).drop(2) == List(3)) assert(List(1, 2, 3).take(2) == List(1, 2)) assert(List(1, 2, 3).dropRight(2) == List(1)) assert(List(1, 2, 3).takeRight(2) == List(2, 3)) assert((1 to 5).take(2) == (1 to 2))`

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

`assert(Option(1).flatMap(x => Option(x + 2)) == Option(3)) assert(Option(1).flatMap(x => None) == None)`

- 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")`

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

## Algorithm in Scala

29 lines of Scala (version 2.13), showing how concise Scala can be!

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

```
def findMinAvgSlice(input: Int*): Option[SubSlice] = ???
```