1539. Kth Missing Positive Number - Detailed Explanation

Problem Statement

You are given an array arr of positive integers sorted in strictly increasing order and an integer k. The task is to return the kth missing positive number starting from 1.

A positive number is considered missing if it is not present in the array.

Examples

Example 1

• Input:
  arr = [2, 3, 4, 7, 11], k = 5
• Output:
  9
• Explanation:
  The missing positive numbers are [1, 5, 6, 8, 9, 10, 12, ...].
  The 5th missing positive number is 9.

Example 2

• Input:
  arr = [1, 2, 3, 4], k = 2
• Output:
  6
• Explanation:
  The missing positive numbers after 4 are [5, 6, 7, ...].
  The 2nd missing positive number is 6.

Constraints

• (1 \leq \text{arr.length} \leq 1000)

• (1 \leq \text{arr}[i] \leq 1000)

• (1 \leq k \leq 1000)

• arr is sorted in strictly increasing order.

Hints

1. Missing Count at Each Position:
   For any index i in the array, the number of positive integers missing before arr[i] is given by:
   [ \text{missing} = \text{arr}[i] - (i + 1) ] This is because if no numbers were missing, the value at index i should be (i + 1).

2. Linear Scan:
   Iterate through the array and check if the kth missing number falls before the current element. If not, adjust k by subtracting the number of missing numbers up to that point.

3. Binary Search:
   Use binary search on the array to quickly locate the smallest index where the missing count is at least k. Then, the kth missing number can be computed from that index.

Approaches

Approach 1: Linear Scan

1. Iterate Through the Array:
   For each element in the sorted array, calculate the number of missing numbers up to that element using: [ \text{missing} = \text{arr}[i] - (i + 1) ]

2. Check for kth Missing:

   • If k is greater than the missing count at the current index, subtract that count from k and continue.

   • If the missing count reaches or exceeds k before you finish scanning, the kth missing number is found in the gap before arr[i].

3. Beyond the Array:
   If you finish the loop, the kth missing number lies after the last element. In that case, it is: [ \text{arr}[n-1] + k ] where n is the length of arr.

Approach 2: Binary Search

1. Missing Function:
   For an index i, compute the missing count as: [ \text{missing}(i) = \text{arr}[i] - (i + 1) ]

2. Binary Search for the Breakpoint:
   Find the smallest index low such that missing(low) >= k.

   • If such an index is found, the kth missing number is: [ k + \text{low} ]
   • If no such index exists (i.e. k is larger than the missing count up to the last element), the answer is: [ \text{arr}[n-1] + (k - \text{missing}(n-1)) ]

Step-by-Step Walkthrough (Linear Scan)

Consider arr = [2, 3, 4, 7, 11] and k = 5.

1. Index 0:

   • arr[0] = 2
   • Missing count = (2 - (0 + 1) = 1)
   • Since (k = 5 > 1), subtract 1 from k. Now, k = 4.

2. Index 1:

   • arr[1] = 3
   • Missing count = (3 - (1 + 1) = 1)
   • The total missing numbers up to index 1 is still 1 (because no additional missing number is added since 3 is exactly one more than 2).
   • Continue.

3. Index 2:

   • arr[2] = 4
   • Missing count = (4 - (2 + 1) = 1)
   • Still, the missing count remains 1 overall up to here.
   • Continue.

4. Index 3:

   • arr[3] = 7

   • Missing count = (7 - (3 + 1) = 7 - 4 = 3)

   • Now, missing numbers in the gap between 4 and 7 are: [5, 6].

   • Total missing count up to index 3 becomes 3.

   • We already subtracted 1 earlier, and now the new gap contributes 2 missing numbers. Update k accordingly.

   • At this point, before index 3, we had (k = 4) remaining.

   • The gap between 4 and 7 adds 2 missing numbers. If (k) is still greater than 2, subtract 2 from k: now k = 4 - 2 = 2.

5. Index 4:

   • arr[4] = 11
   • Missing count = (11 - (4 + 1) = 11 - 5 = 6)
   • The gap between 7 and 11 gives missing numbers: [8, 9, 10, ...].
   • Now (k = 2) falls into this gap.
   • Therefore, the kth missing number is:
     [ 7 + k = 7 + 2 = 9 ]

Result: The kth missing positive number is 9.

Code Implementation

Python Code