Kth Missing Positive Number

🎯

Kth Missing Positive Number

easyCYCLIC_SORTAmazonGoogle

Imagine you are tracking attendance numbers in a classroom, but some students are absent. You want to find the kth student number that never showed up.

💡 This problem asks for the kth missing positive integer from a sorted or unsorted array. Beginners often struggle because it requires understanding how to count missing numbers efficiently rather than just scanning the array.

📋

Problem Statement

Given an array arr of positive integers sorted in strictly increasing order, and an integer k, return the kth positive integer that is missing from this array.

1 ≤ arr.length ≤ 10^51 ≤ arr[i] ≤ 10^7arr is sorted in strictly increasing order1 ≤ k ≤ 10^8

💡

Example

Input"arr = [2,3,4,7,11], k = 5"

Output9

The missing positive integers are [1,5,6,8,9,10,12,...]. The 5th missing is 9.

Input"arr = [1,2,3,4], k = 2"

Output6

The missing positive integers are [5,6,7,...]. The 2nd missing is 6.

• arr contains no missing numbers before last element → kth missing is after last element
• k is smaller than the first missing number → kth missing is less than arr[0]
• arr has only one element → missing numbers before and after it
• k is very large → missing number beyond the last element

⚠️

Common Mistakes

Not handling missing numbers before the first array element

Incorrect answer when kth missing is less than arr[0]

✅ Check missing count before first element and handle separately

Using linear scan brute force for large k

Time limit exceeded or very slow runtime

✅ Use missing count formula or binary search to optimize

Off-by-one errors in missing count calculation

Wrong kth missing number returned

✅ Carefully use arr[i] - (i + 1) formula and test with examples

Not updating binary search boundaries correctly

Infinite loop or wrong answer

✅ Ensure low and high pointers move correctly based on missing count comparison

Returning k + low instead of k + high + 1 after binary search

Incorrect kth missing number

✅ Return k + high + 1 as per binary search final state

🧠

Brute Force (Linear Scan Counting Missing)

💡 This approach exists to build intuition by simulating the counting of missing numbers one by one, which is straightforward but inefficient.

Intuition

We iterate from 1 upwards, checking if each number is in the array. If not, we count it as missing until we reach the kth missing number.

Algorithm

1. Initialize a pointer for the array and a counter for missing numbers.
2. Iterate from 1 upwards, checking if current number matches array element.
3. If it matches, move array pointer forward; else increment missing count.
4. When missing count reaches k, return the current number.

💡 This algorithm is easy to understand but inefficient because it checks every number one by one.

</>

Code

def findKthPositive(arr, k):
    missing_count = 0
    current = 1
    i = 0
    n = len(arr)
    while True:
        if i < n and arr[i] == current:
            i += 1
        else:
            missing_count += 1
            if missing_count == k:
                return current
        current += 1

# Driver code
if __name__ == '__main__':
    print(findKthPositive([2,3,4,7,11], 5))  # Output: 9

Line Notes

missing_count = 0Initialize count of missing numbers found so far

current = 1Start checking from the smallest positive integer

if i < n and arr[i] == currentCheck if current number is present in array

missing_count += 1Increment missing count when current number is not in array

if missing_count == kReturn current number when kth missing is found

public class Solution {
    public static int findKthPositive(int[] arr, int k) {
        int missingCount = 0, current = 1, i = 0, n = arr.length;
        while (true) {
            if (i < n && arr[i] == current) {
                i++;
            } else {
                missingCount++;
                if (missingCount == k) return current;
            }
            current++;
        }
    }

    public static void main(String[] args) {
        System.out.println(findKthPositive(new int[]{2,3,4,7,11}, 5)); // 9
    }
}

Line Notes

int missingCount = 0Initialize missing count to zero

int current = 1Start checking from 1

if (i < n && arr[i] == current)Check if current number is in array

missingCount++Increment missing count if current is missing

if (missingCount == k) return currentReturn when kth missing found

#include <iostream>
#include <vector>
using namespace std;

int findKthPositive(vector<int>& arr, int k) {
    int missingCount = 0, current = 1, i = 0, n = arr.size();
    while (true) {
        if (i < n && arr[i] == current) {
            i++;
        } else {
            missingCount++;
            if (missingCount == k) return current;
        }
        current++;
    }
}

int main() {
    vector<int> arr = {2,3,4,7,11};
    cout << findKthPositive(arr, 5) << endl; // 9
    return 0;
}

Line Notes

int missingCount = 0Initialize missing count

int current = 1Start from smallest positive integer

if (i < n && arr[i] == current)Check if current number is in array

missingCount++Increment missing count if current missing

if (missingCount == k) return currentReturn kth missing number

function findKthPositive(arr, k) {
    let missingCount = 0, current = 1, i = 0, n = arr.length;
    while (true) {
        if (i < n && arr[i] === current) {
            i++;
        } else {
            missingCount++;
            if (missingCount === k) return current;
        }
        current++;
    }
}

// Test
console.log(findKthPositive([2,3,4,7,11], 5)); // 9

Line Notes

let missingCount = 0Initialize missing count

let current = 1Start checking from 1

if (i < n && arr[i] === current)Check if current number is in array

missingCount++Increment missing count if current missing

if (missingCount === k) return currentReturn kth missing number

⏱

Complexity

TimeO(k + n)

SpaceO(1)

We potentially iterate up to k missing numbers plus array traversal. If k is large, this is inefficient.

💡 For n=5 and k=5, this means up to 10 iterations, which is fine for small inputs but slow for large k.

Interview Verdict: TLE for large k, but good for understanding problem

This approach is too slow for large inputs but helps understand the problem and counting missing numbers.

🧠

Better Approach (Using Missing Count Formula and Linear Scan)

💡 This approach improves efficiency by using the formula for missing numbers up to arr[i] instead of checking each number.

Intuition

At each index i, the count of missing numbers before arr[i] is arr[i] - (i + 1). We find where kth missing fits by scanning the array once.

Algorithm

1. Iterate through the array and compute missing count before each element.
2. If kth missing is less than missing count before arr[i], kth missing lies before arr[i].
3. Return k + i as the kth missing number if not found in array gaps.
4. Otherwise, calculate kth missing using the last element and k.

💡 This algorithm uses math to skip unnecessary checks and find the kth missing faster.

</>

Code

def findKthPositive(arr, k):
    n = len(arr)
    for i in range(n):
        missing = arr[i] - (i + 1)
        if missing >= k:
            return k + i
    return k + n

# Driver code
if __name__ == '__main__':
    print(findKthPositive([2,3,4,7,11], 5))  # Output: 9

Line Notes

for i in range(n)Iterate over array indices to check missing counts

missing = arr[i] - (i + 1)Calculate how many numbers are missing before arr[i]

if missing >= kIf kth missing is before arr[i], return answer

return k + nIf kth missing is beyond last element, add k to array length

public class Solution {
    public static int findKthPositive(int[] arr, int k) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int missing = arr[i] - (i + 1);
            if (missing >= k) return k + i;
        }
        return k + n;
    }

    public static void main(String[] args) {
        System.out.println(findKthPositive(new int[]{2,3,4,7,11}, 5)); // 9
    }
}

Line Notes

for (int i = 0; i < n; i++)Loop through array to find missing counts

int missing = arr[i] - (i + 1)Calculate missing numbers before arr[i]

if (missing >= k) return k + iReturn kth missing if it lies before arr[i]

return k + nReturn kth missing beyond last element if not found

#include <iostream>
#include <vector>
using namespace std;

int findKthPositive(vector<int>& arr, int k) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        int missing = arr[i] - (i + 1);
        if (missing >= k) return k + i;
    }
    return k + n;
}

int main() {
    vector<int> arr = {2,3,4,7,11};
    cout << findKthPositive(arr, 5) << endl; // 9
    return 0;
}

Line Notes

for (int i = 0; i < n; i++)Iterate over array to compute missing counts

int missing = arr[i] - (i + 1)Calculate missing numbers before arr[i]

if (missing >= k) return k + iReturn kth missing if it lies before arr[i]

return k + nReturn kth missing beyond last element

function findKthPositive(arr, k) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let missing = arr[i] - (i + 1);
        if (missing >= k) return k + i;
    }
    return k + n;
}

// Test
console.log(findKthPositive([2,3,4,7,11], 5)); // 9

Line Notes

for (let i = 0; i < n; i++)Loop through array indices

let missing = arr[i] - (i + 1)Calculate missing count before arr[i]

if (missing >= k) return k + iReturn kth missing if it lies before arr[i]

return k + nReturn kth missing beyond last element

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the array once, computing missing counts and returning answer early if possible.

💡 For n=5, this means 5 iterations, which is efficient for large k compared to brute force.

Interview Verdict: Accepted and efficient for moderate n

This approach is much faster than brute force and suitable for most interview scenarios.

🧠

Optimal Approach (Binary Search on Missing Count)

💡 This approach uses binary search to find the smallest index where missing count is at least k, optimizing time to O(log n).

Intuition

Since missing count is strictly increasing with index, we can binary search for the first index where missing count >= k, then compute kth missing from that position.

Algorithm

1. Initialize low and high pointers for binary search over array indices.
2. While low <= high, compute mid and missing count before arr[mid].
3. If missing count < k, move low to mid + 1; else move high to mid - 1.
4. After binary search, kth missing is k + high + 1.

💡 Binary search efficiently narrows down the position where kth missing lies by comparing missing counts.

</>

Code

def findKthPositive(arr, k):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        missing = arr[mid] - (mid + 1)
        if missing < k:
            low = mid + 1
        else:
            high = mid - 1
    return k + high + 1

# Driver code
if __name__ == '__main__':
    print(findKthPositive([2,3,4,7,11], 5))  # Output: 9

Line Notes

low, high = 0, len(arr) - 1Initialize binary search boundaries

mid = (low + high) // 2Calculate middle index

missing = arr[mid] - (mid + 1)Calculate missing count before arr[mid]

if missing < k: low = mid + 1Move right if kth missing is beyond mid

else: high = mid - 1Move left if kth missing is before or at mid

return k + high + 1Calculate kth missing number after binary search

public class Solution {
    public static int findKthPositive(int[] arr, int k) {
        int low = 0, high = arr.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int missing = arr[mid] - (mid + 1);
            if (missing < k) low = mid + 1;
            else high = mid - 1;
        }
        return k + high + 1;
    }

    public static void main(String[] args) {
        System.out.println(findKthPositive(new int[]{2,3,4,7,11}, 5)); // 9
    }
}

Line Notes

int low = 0, high = arr.length - 1Initialize binary search boundaries

int mid = low + (high - low) / 2Calculate mid index safely

int missing = arr[mid] - (mid + 1)Calculate missing count before arr[mid]

if (missing < k) low = mid + 1Search right half if kth missing beyond mid

else high = mid - 1Search left half if kth missing before or at mid

return k + high + 1Compute kth missing after binary search

#include <iostream>
#include <vector>
using namespace std;

int findKthPositive(vector<int>& arr, int k) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int missing = arr[mid] - (mid + 1);
        if (missing < k) low = mid + 1;
        else high = mid - 1;
    }
    return k + high + 1;
}

int main() {
    vector<int> arr = {2,3,4,7,11};
    cout << findKthPositive(arr, 5) << endl; // 9
    return 0;
}

Line Notes

int low = 0, high = arr.size() - 1Initialize binary search boundaries

int mid = low + (high - low) / 2Calculate mid index safely

int missing = arr[mid] - (mid + 1)Calculate missing count before arr[mid]

if (missing < k) low = mid + 1Search right half if kth missing beyond mid

else high = mid - 1Search left half if kth missing before or at mid

return k + high + 1Compute kth missing after binary search

function findKthPositive(arr, k) {
    let low = 0, high = arr.length - 1;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        let missing = arr[mid] - (mid + 1);
        if (missing < k) low = mid + 1;
        else high = mid - 1;
    }
    return k + high + 1;
}

// Test
console.log(findKthPositive([2,3,4,7,11], 5)); // 9

Line Notes

let low = 0, high = arr.length - 1Initialize binary search boundaries

let mid = Math.floor((low + high) / 2)Calculate mid index

let missing = arr[mid] - (mid + 1)Calculate missing count before arr[mid]

if (missing < k) low = mid + 1Search right half if kth missing beyond mid

else high = mid - 1Search left half if kth missing before or at mid

return k + high + 1Compute kth missing after binary search

⏱

Complexity

TimeO(log n)

SpaceO(1)

Binary search reduces the search space exponentially, making it efficient for large arrays.

💡 For n=10^5, this means about 17 iterations, which is very fast.

Interview Verdict: Accepted and optimal for large inputs

This is the best approach to implement in interviews for efficiency and clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the binary search approach is best for efficiency and clarity; mention brute force to show understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(k + n)	O(1)	No	N/A	Mention only - never code for large inputs
2. Missing Count Linear Scan	O(n)	O(1)	No	N/A	Good for moderate input sizes
3. Binary Search on Missing Count	O(log n)	O(1)	No	N/A	Optimal approach to code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Explain the missing count formula and linear scan optimization.Step 4: Present the binary search approach as the optimal solution.Step 5: Code the binary search solution carefully and test edge cases.

Time Allocation

Clarify: 2min → Approach discussion: 5min → Code: 10min → Testing & edge cases: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize, and coding accuracy, especially handling edge cases and large inputs.

Common Follow-ups

• What if the array is not sorted? → Sort first or use a hash set.
• Can you find all missing numbers up to k? → Modify approach to collect missing numbers.

💡 These follow-ups test adaptability and deeper understanding of missing number problems.

🔍

Pattern Recognition

When to Use

1) Input is sorted array of positive integers, 2) Need to find kth missing positive, 3) Missing numbers form a complement set, 4) Counting missing numbers can be done via index-value difference.

Signature Phrases

'kth positive integer that is missing''missing positive integers in sorted array'

NOT This Pattern When

Problems asking for missing numbers in unsorted arrays without order or kth smallest missing without sorted input

Similar Problems

First Missing Positive - find smallest missing positive integer using cyclic sortMissing Number - find single missing number in sequence using sum or XORFind All Missing Numbers - find all missing numbers using cyclic sort or hash

Practice

1. You are given an array containing numbers from 1 to n, but some numbers appear twice and others are missing. Which algorithmic approach guarantees finding all missing numbers in O(n) time and O(1) extra space?

easy

A. In-place cyclic sort that places each number at its correct index

B. Sorting the array and then scanning for missing numbers

C. Using a hash set to track presence of numbers

D. Dynamic programming to count occurrences and identify missing numbers

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 1 to n with duplicates and missing numbers, requiring an O(n) time and O(1) space solution.

2. Step 2: Identify the approach that fits constraints

   In-place cyclic sort rearranges numbers so each number is at index = number - 1, enabling detection of missing numbers without extra space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only cyclic sort achieves O(n) time and O(1) space for this problem [OK]

Hint: Optimal approach uses in-place cyclic sort [OK]

Common Mistakes:

• Assuming sorting is O(n) time
• Using extra space violates O(1) space
• Confusing DP with counting problems

2. You are given an array containing numbers from 1 to n with exactly one number duplicated and one number missing. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution to find both the duplicate and missing numbers?

easy

A. Sorting the array and then scanning for the mismatch

B. Using a hash set to track seen numbers and then find the duplicate and missing

C. Brute force nested loops counting occurrences of each number

D. Cyclic sort to place each number at its correct index and then identify the mismatch

Solution

1. Step 1: Understand problem constraints

   The array contains numbers 1 to n with one duplicate and one missing number.

2. Step 2: Identify approach that achieves O(n) time and O(1) space

   Cyclic sort places each number at its correct index in one pass, then a second pass finds the mismatch efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort rearranges in-place and finds mismatch in linear time [OK]

Hint: Cyclic sort solves this in linear time and constant space [OK]

Common Mistakes:

• Assuming sorting is always optimal despite O(n log n) time
• Using hash sets increases space complexity
• Brute force is too slow for large inputs

3. Given the following code snippet, what is the output when calling findDuplicate([2, 1, 4, 3, 2])?

easy

A. 2

B. -1

C. 3

D. 1

Solution

1. Step 1: Trace initial array and i=0

   nums = [2,1,4,3,2], i=0, correct_index=1. nums[0]=2 != nums[1]=1, swap -> nums=[1,2,4,3,2]

2. Step 2: i=0 again, correct_index=0, nums[0]=1 == nums[0]=1, i=1

   i=1, correct_index=1, nums[1]=2 == nums[1]=2, i=2

3. Step 3: i=2, correct_index=3, nums[2]=4 != nums[3]=3, swap -> nums=[1,2,3,4,2]

   i=2 again

4. Step 4: i=2, correct_index=2, nums[2]=3 == nums[2]=3, i=3

   i=3, correct_index=3, nums[3]=4 == nums[3]=4, i=4

5. Step 5: i=4, correct_index=1, nums[4]=2 == nums[1]=2, i != correct_index -> duplicate found: 2

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Duplicate 2 correctly identified [OK]

Hint: Swapping places elements until duplicate found [OK]

Common Mistakes:

• Returning wrong duplicate due to off-by-one index
• Incrementing i too early causing missed duplicates
• Confusing value and index during swaps

4. Given the following code snippet implementing the optimal cyclic sort approach, what is the returned output when the input is [3, 4, -1, 1]?

def find_smallest_missing_range(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct_pos = nums[i] - 1
        if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
        else:
            i += 1
    start = 1
    for i in range(n):
        if nums[i] != i + 1:
            start = i + 1
            break
    else:
        return [n + 1, n + 1]
    end = start
    while end <= n and nums[end - 1] != end:
        end += 1
    return [start, end - 1]

print(find_smallest_missing_range([3, 4, -1, 1]))

easy

A. [4, 4]

B. [1, 1]

C. [2, 2]

D. [2, 3]

Solution

1. Step 1: Trace cyclic sort swaps

   Initial array: [3,4,-1,1] - i=0: nums[0]=3, correct_pos=2; swap nums[0] and nums[2] -> [-1,4,3,1] - i=0: nums[0]=-1 (not in 1..n), i++ -> i=1 - i=1: nums[1]=4, correct_pos=3; swap nums[1] and nums[3] -> [-1,1,3,4] - i=1: nums[1]=1, correct_pos=0; swap nums[1] and nums[0] -> [1,-1,3,4] - i=1: nums[1]=-1 (not in 1..n), i++ -> i=2 - i=2: nums[2]=3, correct_pos=2; already correct, i++ -> i=3 - i=3: nums[3]=4, correct_pos=3; already correct, i++ -> i=4 (end)

2. Step 2: Find smallest missing positive range

   Array after sorting: [1, -1, 3, 4] Check indices: - i=0: nums[0]=1 correct - i=1: nums[1]=-1 != 2 -> start=2 Find end: - end=2: nums[1]=-1 != 2 -> end=3 - end=3: nums[2]=3 == 3 -> stop Return [2, 2]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected missing smallest positive range [2, 2] [OK]

Hint: Trace swaps carefully to find final array state [OK]

Common Mistakes:

• Off-by-one in start or end calculation
• Ignoring negative numbers during swaps

5. What is the time complexity of the cyclic sort approach to find the duplicate number in an array of size n, and why?

medium

A. O(n^2) because each swap can cause another iteration over the array

B. O(n log n) due to sorting-like behavior of swaps

C. O(n) because each number is swapped at most once to its correct position

D. O(n) but with O(n) extra space for tracking swaps

Solution

1. Step 1: Analyze the number of swaps

   Each element is swapped at most once to its correct index, so total swaps ≤ n.

2. Step 2: Confirm linear time complexity

   Since each iteration either swaps or increments index, total operations are O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear time due to limited swaps and single pass [OK]

Hint: Each element moves at most once -> O(n) time [OK]

Common Mistakes:

• Assuming swaps cause nested loops leading to O(n²)
• Confusing swaps with sorting complexity O(n log n)
• Forgetting that no extra space is used