MissingInteger: Find the smallest positive integer that does not occur in a given sequence

MissingInteger.md

Write a function:

function solution(A);

that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

    `N` is an integer within the range `[1..100,000]`;
    each element of array `A` is an integer within the range `[−1,000,000..1,000,000]`.

solution.js

class MinimumNumberTracker {
  constructor() {
    /**
     * Relies on the implicit insertion ordering for the iterator,
     * so that when we complete the operations across all numbers,
     * we can simply return the first number in the list.
     */
    this._numberTracker = {};

    /**
     * Holds the value of the maximum number added to the tracker
     * directly.
     */
    this._maximumTrackerNumber = 0;
  }

  /**
   * Tracks the provided integer
   *
   * @param {*} number
   */
  track(number) {
    // adds the number for cases where necessary
    this._add(number);

    // since the number itself was added, it is not itself valid as
    // the minimum number to not exist in the input list
    this._remove(number);
  }

  /**
   * Retrieves the minimum positive integer from the tracker
   *
   * @returns the minimum positive integer
   */
  getMinimum() {
    for (let i in this._numberTracker) {
      return parseInt(i);
    }

    return this._maximumTrackerNumber + 1;
  }

  /**
   * Adds the provided number to the number tracker, expanding the range
   * if it exceeds the current maximum tracked number.
   *
   * @param {*} number
   * @returns
   */
  _add(number) {
    // we will not track non-positive integers
    if (number <= 0) {
      return;
    }

    // we do not need to take any action on already tracked numbers
    if (this._numberTracker[number]) {
      return;
    }

    // non-positive integers less than the maximum are already tracked
    if (number <= this._maximumTrackerNumber) {
      return;
    }

    // expand the tracker to include all integers up to the provided
    // number and update the current maximum in the tracker
    for (let i = this._maximumTrackerNumber + 1; i <= number; i++) {
      this._numberTracker[i] = true;
    }
    this._maximumTrackerNumber = number;
  }

  /**
   * Removes the provided number from the number tracker
   * @param {*} number
   */
  _remove(number) {
    if (number in this._numberTracker) {
      delete this._numberTracker[number];
    }
  }
}

function solution(numberArray) {
  const existingNumbers = new MinimumNumberTracker();

  for (let index = 0; index < numberArray.length; index++) {
    const currentNumber = numberArray[index];
    existingNumbers.track(currentNumber);
  }

  return existingNumbers.getMinimum();
}