Project Find Next Missing Integer In Array

Package - findNextMissingIntegerInArray

Problem Overview

This package aims to solve the following problem

• Given an array of integers, find the first missing positive integer in linear time and constant space.
• In other words, find the lowest positive integer that does not exist in the array.
• The array can contain duplicates and negative numbers as well.

Interpreted this as

• if there is array with positives in it, then find next lowest missing inter that is greater than lowest positive.
• if the existing array positive starts at N, and there are no missing integers, then return one moe thnthe greatest number
• if there is only 1 positive then return 1 greater
• if there are no positive numbers (> 0) then return 0.

Solution approach

• Put the numbers into a Set, and then sort the set - use a Treeset - gets rid of duplicates.
• Then use a stream and get get a set that only has positive values - here I treat 0 as not being positive
• Then check to see if it is contiguous based on size and considering highest and lowset entries -
• If contiguous, then return the next value up.
• If not contiguous, start at the beginning and calculate the next value up - if if is not just a single value up, return the missing value.