Home

오늘의 기억

[Algorithm] MissingInteger


Question

This is a demo task.

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 (TypeScript)

function solution(n: number[]): number {
  let target = 1;
  const tmp = {};

  function nextTarget() {
    while (true) {
      target += 1;
      if (!tmp[target]) {
        return;
      }
    }
  }

  for(const val of n) {
    if (target === val) {
      nextTarget();
    }
    tmp[val] = true;
  }
  return target;
}

Author: Codility, Lesson 4

20200108 Charyum.Park