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.

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

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

Get the full algorithm Scala algorithms logo, maze part, which looks quirky!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Stripe logo

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.

View the rest of Scala algorithms