How to Solve LeetCode 1539: Kth Missing Positive Number in JavaScript

A Step-by-Step Guide with Code Walk Through

In this Leetcode problem, we’re told that we’re given an ordered array of positive integers that has some missing numbers as input, along with a number (k). Our task: find the kth missing number in that input array. Sounds more complicated than it is. Let’s get at it.

Let’s say we have an array with the number [1, 2, 3, 4], and we’re told to find the 2nd missing number. Confusing. Doesn’t seem like there is a missing number in that array.

We’d have to assume that the two missing number are 5 and 6, and thus, the 2nd missing number is 6, and the full array would actually be [1, 2, 3, 4, 5, 6].

What’s the Algorithm?

As a human, if you’re tasked to find the kth missing numbers in a sequence, I’d argue you’d do something like,

1. Start from 1, counting up
2. When a number seems to be missing, make note of it by incrementing an internal counter.
3. When you’ve reached the number of missing numbers you were asked to find, stop, and say which number should’ve been there.

Coding a Solution

Let’s initialize a function called findKthPositive that takes in an array (arr) and a number (k) as input. And, as described above, we’re going to need to count how many numbers are missing in our sequence, so let’s initialize a missingCounter variable:

function findKthPositive(arr, k) {
  let missingCounter = 0;
}

Next, we have to walk through our sequence. Let’s do that with a for loop. Typically we setup a for loop to run the entire length of an array. But what do we do when our array has missing values?

One way is to tell our for loop to keep running while a condition hasn’t been met. That condition should be to keep going, while I haven’t reached the amount of missing numbers that k tells me:

function findKthPositive(arr, k) {
  let missingCounter = 0;
for (let i = 1; missingCounter != k; i++) {

  }
}

Also, because the problem states we’re getting positive integers as an input, we can go ahead and start at 1, instead of 0 like we normally do.

Next, we’re going to test if the number we’re currently iterating with is in the array. If it’s not, we should increment our missingCounter. And we’ll keep doing that until our missingCounter = k:

function findKthPositive(arr, k) {
  let missingCounter = 0;
for (let i = 1; missingCounter != k; i++) {
    if (!arr.includes(i)) missingCounter++;
    if (missingCounter === k) return i;
  }
}

At the moment the missingCounter = k, we’ve found that missing number, and we should return it.

Code Walkthrough

If this is still a bit abstract, let’s walk through the example.

• We’ve initialized our missingCounter variable with 0, and entered a for loop with i = 1, since 0 ≠ 2.
• We meet the conditional: is 1 in our array? It is, so we don’t increment the missingCounter.
• We’ve already agreed 0 ≠ 2 so we don’t return anything, and go back up the loop.
• Now i = 2. Is 2 in the array? It is, so we so we don’t increment the missingCounter.
• missingCounter is still 0. 0 ≠ 2 so we don’t return anything, and go back up the loop.
• Now i = 3. Is 3 in the array? It is, so we so we don’t increment the missingCounter.
• missingCounter is still 0. 0 ≠ 2 so we don’t return anything, and go back up the loop.
• Now i = 4. Is 4 in the array? It is, so we so we don’t increment the missingCounter.
• missingCounter is still 0. 0 ≠ 2 so we don’t return anything, and go back up the loop.
• Now i = 5. Is 5 in the array? It is not. So this time we increment missingCounter to 1.
• missingCounter is now 1. 1≠ 2 so we don’t return anything, and go back up the loop.
• Now i = 6. Is 6 in the array? It is not. So this time we increment missingCounter to 2.
• missingCounter is now 2. 2 = 2 so now return i, which is 6.

Questions? Leave them in the comment. Thanks for reading!

And remember…

Grit > talent.