JavaScript Missing Numbers Finder: Two Approaches Quiz
Find missing integers between the min and max of an array, two ways (sort + gap-walk and Set diff over min..max), plus companions on the consecutive-1..n case and detecting duplicates.
227 views
1
Implement missingNumbers(arr) using SORT + a GAP WALK: sort numerically, then iterate from min to max and collect every integer absent from the sorted array.
Examples
Example 1:
Input: [1, 7, 3, 6]
Output: [2, 4, 5]
Explanation: Range is 1..7; missing integers are 2, 4, 5.Example 2:
Input: [5, 0, -3, 2]
Output: [-2, -1, 1, 3, 4]
Explanation: Range is -3..5; missing integers are -2, -1, 1, 3, 4.function missingNumbers(arr) {
// sort numerically + walk from min to max, push absentees
}Implement missingNumbersBySet(arr) using Math.min + Math.max + a Set for O(1) lookups, walking the range and collecting absentees. Why is this strictly better than a sort + Array.prototype.includes approach on large inputs?
Examples
Example 1:
Input: [1, 3, 5]
Output: [2, 4]
Explanation: Range is 1..5; 2 and 4 are missing.function missingNumbers(arr) {
// Set + Math.min/max + range walk
}Implement findMissingInOneToN(arr, n) where the caller asserts arr should hold every integer from 1..n with exactly ONE missing. Return that missing integer in O(n) time and O(1) extra space using the Gauss sum.
Examples
Example 1:
Input: arr = [1, 2, 4, 5], n = 5
Output: 3
Explanation: Expected sum 1+2+3+4+5 = 15; actual sum 12; missing = 15 - 12 = 3.function findMissingInOneToN(arr, n) {
// Gauss sum: expected - actual
}Implement findDuplicates(arr) that returns the values appearing more than once, in their first-seen order. Use a single pass with a Set of seen values plus a Set of already-reported duplicates.
Examples
Example 1:
Input: [1, 2, 3, 2, 4, 3, 5, 2]
Output: [2, 3]
Explanation: 2 first repeats at index 3; 3 first repeats at index 5; 2 is not reported again at index 7.function findDuplicates(arr) {
// two-Set single pass
}