Find K Missing Positive Numbers

📋

Find K Missing Positive Numbers

Edge cases:

</>

IDE

def find_k_missing_numbers(arr: list[int], k: int) -> list[int]:public int[] findKMissingNumbers(int[] arr, int k)vector<int> findKMissingNumbers(vector<int>& arr, int k)function findKMissingNumbers(arr, k)

def find_k_missing_numbers(arr, k):
    # Write your solution here
    pass

class Solution {
    public int[] findKMissingNumbers(int[] arr, int k) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> findKMissingNumbers(vector<int>& arr, int k) {
    // Write your solution here
    return {};
}

function findKMissingNumbers(arr, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 2, 3]Code returns first K natural numbers without checking array contents.✅ Use a set to track existing numbers and only add missing numbers not in the set.

Wrong: [2, 3, 4]Code assumes missing numbers start after 1 without checking if 1 is missing.✅ Start checking from 1 upwards and verify presence in the array set.

Wrong: [6, 7, 8]Code fails to find missing numbers within the range and only returns numbers after max element.✅ Check for missing numbers starting from 1, not just after max element.

Wrong: [1, 3]Code counts duplicates multiple times causing incorrect missing count.✅ Use a set to avoid counting duplicates multiple times.

Wrong: Timeout or no outputInefficient nested loops or repeated membership checks causing TLE.✅ Use O(n + k) approach with set or boolean array for membership checks.

✓

Test Cases

Focus on handling edge cases like empty arrays and single elements.

Watch out for duplicates and off-by-one errors in missing number calculations.

Optimize your solution to handle large inputs efficiently.

t1_01basic

Input{"arr":[3,-1,4,5,5],"k":3}

Expected[1,2,6]

⏱ Performance - must finish in 2000ms

The missing positive numbers are 1, 2, and 6 in ascending order.

💡 Consider using a set to track existing numbers and check sequentially for missing positives.

💡 Use a loop starting from 1 and add numbers not in the set until you have K missing numbers.

💡 Maintain a current number counter and append to result if not in set until length K.

Why it failed: Incorrect output likely due to not handling duplicates or negative numbers properly; fix by using a set and checking only positive numbers.

✓ Correctly identifies missing positive numbers including handling duplicates and negatives.

t1_02basic

Input{"arr":[2,3,7,6,8,-1,-10,15],"k":5}

Expected[1,4,5,9,10]

⏱ Performance - must finish in 2000ms

Missing positive numbers are 1, 4, 5, 9, and 10 in ascending order.

💡 Filter out non-positive numbers and use a set for quick membership checks.

💡 Iterate from 1 upwards, adding missing numbers until K are found.

💡 Remember to skip numbers present in the array and handle gaps between max elements.

Why it failed: Fails if code does not correctly skip negative numbers or duplicates; fix by filtering and using a set.

✓ Correctly finds first K missing positive numbers even with negative and large values.

t2_01edge

Input{"arr":[],"k":4}

Expected[1,2,3,4]

⏱ Performance - must finish in 2000ms

Empty array means first K positive numbers starting from 1 are missing.

💡 If array is empty, missing numbers start from 1 sequentially.

💡 No elements to exclude, so just return [1..K].

💡 Initialize current number at 1 and add until K missing numbers collected.

Why it failed: Fails if code does not handle empty input; fix by returning range 1 to K when array is empty.

✓ Correctly returns first K positive numbers for empty input.

t2_02edge

Input{"arr":[1],"k":1}

Expected[2]

⏱ Performance - must finish in 2000ms

Array has single element 1, so next missing positive is 2.

💡 Check if 1 is present; if yes, next missing positive starts from 2.

💡 Use set membership to verify presence of numbers.

💡 Return the first missing positive number after the max element.

Why it failed: Fails if code assumes missing numbers start at 1 always; fix by checking presence of 1 and incrementing accordingly.

✓ Correctly handles single element arrays.

t2_03edge

Input{"arr":[1,2,3,4,5],"k":3}

Expected[6,7,8]

⏱ Performance - must finish in 2000ms

All consecutive numbers from 1 to 5 present; missing numbers start after max element 5.

💡 When array contains consecutive numbers from 1, missing numbers start after max element.

💡 Find max element and generate missing numbers starting from max+1.

💡 Use set to confirm no missing numbers within the range.

Why it failed: Fails if code does not handle exact boundary of consecutive numbers; fix by starting missing search after max element.

✓ Correctly identifies missing numbers after max consecutive sequence.

t2_04edge

Input{"arr":[2,2,2,2],"k":2}

Expected[1,3]

⏱ Performance - must finish in 2000ms

Duplicates of 2 present; missing numbers are 1 and 3.

💡 Duplicates should not inflate presence count; use a set to avoid duplicates.

💡 Check for missing numbers starting from 1 regardless of duplicates.

💡 Add missing numbers sequentially until K found, ignoring duplicates.

Why it failed: Fails if duplicates cause incorrect counting of present numbers; fix by using a set to track unique elements.

✓ Correctly handles duplicates without affecting missing count.

t3_01corner

Input{"arr":[1,1,2,2,3,3],"k":3}

Expected[4,5,6]

⏱ Performance - must finish in 2000ms

Duplicates of 1,2,3 present; missing numbers start after max element 3.

💡 Duplicates do not affect missing numbers; focus on unique elements.

💡 After confirming presence of 1 to 3, missing numbers start at 4.

💡 Use set and iterate from max+1 to find missing numbers.

Why it failed: Fails if duplicates cause off-by-one errors in missing count; fix by using set and starting missing search after max element.

✓ Correctly handles duplicates and finds missing numbers after max.

t3_02corner

Input{"arr":[1,2,3,4,5],"k":5}

Expected[6,7,8,9,10]

⏱ Performance - must finish in 2000ms

All numbers 1 to 5 present; missing numbers start after max element 5.

💡 Check if all numbers from 1 to max are present.

💡 If yes, missing numbers start from max+1.

💡 Generate missing numbers sequentially after max element.

Why it failed: Fails if code stops after finding fewer missing numbers than K; fix by continuing search beyond max element until K missing found.

✓ Correctly finds all K missing numbers even when array is consecutive.

t3_03corner

Input{"arr":[3,4,-1,1],"k":2}

Expected[2,5]

⏱ Performance - must finish in 2000ms

Array with negatives and missing numbers; missing are 2 and 5.

💡 Ignore negative numbers and zeros when checking presence.

💡 Use set to track positive numbers and find missing starting from 1.

💡 Continue searching beyond max element if needed to find K missing.

Why it failed: Fails if negatives are included or missing numbers within range are skipped; fix by filtering positives and checking sequentially.

✓ Correctly handles negatives and finds missing numbers.

t4_01performance

Input{"arr":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100000],"k":100000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000, k=100000; solution must run in O(n + k) time within 2 seconds.

💡 Use a set or boolean array for O(1) membership checks.

💡 Avoid nested loops; use linear scans and direct indexing.

💡 Preprocessing with cyclic sort or set membership is key to performance.

Why it failed: TLE due to O(n*k) or worse complexity; fix by using O(n + k) approach with set or boolean array.

✓ Solution runs efficiently in O(n + k) time.

Practice

1. You are given an array of size n containing numbers from 1 to n with exactly one number duplicated and one number missing. Which algorithmic approach guarantees finding both the duplicate and missing numbers in O(n) time and O(1) extra space?

easy

A. Using cyclic sort to place each number at its correct index and then scanning for mismatch

B. Sorting the array and then scanning for the duplicate and missing numbers

C. Using a dynamic programming approach to track counts of each number

D. Using a greedy approach to pick numbers and mark visited elements

Solution

1. Step 1: Understand problem constraints

   The array has numbers from 1 to n with one duplicate and one missing number, so placing each number at its correct index reveals the corrupt pair.

2. Step 2: Identify the best approach

   Cyclic sort places each number at index = number - 1 in O(n) time and O(1) space, enabling detection of the mismatch directly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cyclic sort is optimal for this problem pattern [OK]

Hint: Cyclic sort fits missing+duplicate in O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is always optimal
• Confusing DP with counting
• Using greedy without index placement

2. 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

3. You are given an unsorted array of integers that may contain duplicates, negatives, and zeros. Your task is to find the smallest continuous range of positive integers that are missing from the array. Which algorithmic approach guarantees an optimal O(n) time and O(1) space solution for this problem?

easy

A. Using a hash set to store all positive numbers and then checking for the missing range

B. Sorting the array and then scanning linearly to find the missing range

C. Using a dynamic programming approach to track presence of numbers

D. Using cyclic sort to place each positive integer at its correct index and then scanning for the missing range

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the smallest missing positive range in O(n) time and O(1) space, which excludes sorting (O(n log n)) and hash sets (O(n) space).

2. Step 2: Identify the algorithm that achieves in-place linear time

   Cyclic sort places each positive integer at its correct index in the array, enabling a single pass to find the missing range efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort is known for in-place linear time sorting of numbers in range 1 to n [OK]

Hint: Cyclic sort achieves O(n) time and O(1) space for this problem [OK]

Common Mistakes:

• Assuming sorting is optimal
• Confusing hash set space with time complexity

4. Consider the following code snippet implementing the optimal approach for finding the first missing positive integer. What is the output when the input is [3, 4, -1, 1]?

easy

A. 2

B. 4

C. 3

D. 1

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [3,4,-1,1] - i=0: nums[0]=3, swap nums[2] and nums[0] -> [-1,4,3,1] - i=0 again: nums[0]=-1 (out of range), move on - i=1: nums[1]=4, swap nums[3] and nums[1] -> [-1,1,3,4] - i=1 again: nums[1]=1, swap nums[0] and nums[1] -> [1,-1,3,4] - i=1 again: nums[1]=-1 (out of range), move on - i=2 and i=3 no swaps needed

2. Step 2: Scan for first missing positive

   Array after rearrangement: [1,-1,3,4] Check indices: - i=0: nums[0]=1 (correct) - i=1: nums[1]=-1 (incorrect), so return i+1=2

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected missing positive 2 [OK]

Hint: After cyclic sort, first mismatch index + 1 is missing positive [OK]

Common Mistakes:

• Off-by-one errors in return value
• Not handling negative or out-of-range values
• Infinite loops due to missing swap condition

5. Suppose the input array can contain duplicate numbers and numbers outside the range 0 to n, or the array is immutable. Which modification to the cyclic sort approach correctly finds the missing number under these constraints?

hard

A. Use the sum formula approach since cyclic sort requires unique numbers and mutable array

B. Modify cyclic sort to skip numbers outside 0 to n and duplicates, swapping only valid numbers

C. Use a hash set to track all numbers and then find the missing one in O(n) time and O(n) space

D. Sort the array using built-in sort and scan for missing number, ignoring duplicates

Solution

1. Step 1: Understand constraints

   Duplicates and out-of-range numbers break cyclic sort assumptions; immutability prevents in-place swaps.

2. Step 2: Choose approach handling duplicates and immutability

   Hash set tracks presence without modifying input, handling duplicates and invalid numbers safely.

3. Step 3: Analyze tradeoffs

   Hash set uses O(n) space but guarantees correctness under constraints where cyclic sort fails.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Hash set approach works with duplicates and immutable inputs [OK]

Hint: Cyclic sort requires unique, mutable arrays [OK]

Common Mistakes:

• Trying to adapt cyclic sort without handling duplicates
• Assuming sum formula always works with duplicates
• Ignoring immutability constraints