Scala algorithm: Find minimum missing positive number in a sequence

Published

Algorithm goal

Find the minimum missing positive number in a sequence.

For example, $$[-3,-2]$$ has no minimum missing positive as 1.

$$[-3,1]$$ has minimum missing positive number as $$2$$.

$$[-3,1,3]$$ has minimum missing positive number as $$2$$ as well.

Test cases in Scala

assert(minimumMissing(-3, -2) == 1)
assert(minimumMissing(-3, 1) == 2)
assert(minimumMissing(1, 2, 3) == 4)
assert(minimumMissing(1, 2, 4) == 3)


Algorithm in Scala

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

Explanation

Effectively, what we need to check is to find the first number in range (1 to <maximum positive number that is present>) that is not in the input list..

This means we compute the maximum positive number, and following that, get a set of all numbers (so we can check element presence quickly). (this is © from www.scala-algorithms.com)

Scala concepts & Hints

1. Range

The (1 to n) syntax produces a "Range" which is a representation of a sequence of numbers.

assert((1 to 5).toString == "Range 1 to 5")

assert((1 to 5).reverse.toString() == "Range 5 to 1 by -1")

assert((1 to 5).toList == List(1, 2, 3, 4, 5))

2. View

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

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

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

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

Explore the 21 most useful Scala concepts

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

Register now (free)

Register with GitHub

This gives you access to free test cases & hints for all our 89 published algorithms as well as our installation-free Scala IDE.

You can then choose to subscribe to "Scala Algorithms Unlimited", which gets you access to every current and upcoming algorithm solution. We use Stripe so your data is safe.

We will e-mail you at most once per week with new algorithms and relevant content.
Your data is protected and unsubscribing is straightforward.