Scala algorithm: Find minimum missing positive number in a sequence

Published , last updated

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.

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

Think in Scala & master the highest paid programming language in the US

Scala is used at many places, such as AirBnB, Apple, Bank of America, BBC, Barclays, Capital One, Citibank, Coursera, eBay, JP Morgan, LinkedIn, Morgan Stanley, Netflix, Singapore Exchange, Twitter.

Study our 92 Scala Algorithms: 6 fully free, 74 published & 18 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.