Missing Pair of Integers in Array — Problem Statement & Solution Guide
Problem Description
You are provided with an array of distinct integers, nums, which represents a sequence of consecutive integers starting from 1 up to a maximum value N, with exactly two elements missing. The length of the input array is N - 2. Your task is to identify the two missing integers and return them in ascending order.
The input array is guaranteed to contain unique values, all within the range [1, N], where N is determined by the length of the array plus 2. The solution must efficiently locate the missing values without relying on sorting the entire array or using excessive memory for auxiliary data structures.
Return an array of two integers [a, b] such that a < b, where a and b are the missing values from the original consecutive sequence.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Missing Pair of Integers in Array"
WHY DOES IT MATTER?
Detecting missing elements in a sequence is a classic example of leveraging arithmetic invariants to replace explicit data structures, a skill that translates to many real‑world validation and integrity checks.
OPTIMIZATION CHALLENGE
The key insight is that two unknowns can be solved with two independent aggregates (sum and sum of squares), turning a potentially O(N log N) sorting or O(N) extra‑space problem into a constant‑space linear scan.
REAL-WORLD CONNECTION
In distributed log replication, each log entry is numbered sequentially; spotting gaps (missing entries) quickly without scanning the entire log mirrors this problem and ensures consistency across replicas.
During an interview, compute the two aggregates in a single loop, derive the product of the missing numbers using the algebraic identity, and then solve the quadratic—this shows both mathematical rigor and coding efficiency.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The problem reduces to identifying two missing values from a complete arithmetic progression of length N. A naive scan for each number in the range would be O(N) time and O(1) space, but when N can be as large as 10^7 the constant factor matters, and storing auxiliary structures like hash sets inflates memory usage. The optimal paradigm leverages the mathematical properties of sums and sums of squares: the sum of the first N natural numbers is N(N+1)/2 and the sum of their squares is N(N+1)(2N+1)/6. By computing the difference between the expected totals and the observed totals from the array, we obtain two equations in the two unknown missing numbers, which can be solved in constant time. This approach eliminates the need for extra passes or auxiliary containers, achieving linear time with O(1) auxiliary space.
Interview Questions on This Problem
Q1How would you find two missing numbers from 1..N in O(N) time and O(1) extra space without modifying the input array?
Compute the expected sum S = N(N+1)/2 and expected square sum Sq = N(N+1)(2N+1)/6. Subtract the actual sum and square sum obtained by iterating the array to get diff = S - sum(nums) = a + b and diffSq = Sq - sum(x^2 for x in nums) = a^2 + b^2. Use (a+b)^2 = a^2 + b^2 + 2ab to find ab = ((diff)^2 - diffSq)/2. Now solve the quadratic t^2 - diff*t + ab = 0; its roots are the missing numbers.
Q2If the array could be modified, how would you use the index‑marking technique to locate the two missing integers?
Iterate through the array and for each value v, treat |v| as an index (v-1) and flip the sign of the element at that index to mark its presence. After the pass, indices with positive values correspond to missing numbers (index+1). Since two numbers are missing, you will find exactly two positive entries.
Q3Why might using a hash set to store seen numbers be sub‑optimal for this problem in a production system?
A hash set incurs O(N) additional memory, which can be prohibitive for large N, and the constant‑time overhead of hashing can degrade performance under tight latency constraints. Moreover, it adds GC pressure in managed languages, increasing pause times, whereas the O(1) space solution avoids these issues.
Examples
Input
nums = [1, 2, 4, 5, 6]
Output
[3, 7]
Explanation: The array length is 5, so N = 5 + 2 = 7. The expected sequence is [1, 2, 3, 4, 5, 6, 7]. Comparing with the input, 3 and 7 are absent. Thus, the output is [3, 7].
Input
nums = [1, 3, 4, 5]
Output
[2, 6]
Explanation: The array length is 4, so N = 4 + 2 = 6. The expected sequence is [1, 2, 3, 4, 5, 6]. The input contains 1, 3, 4, 5. The missing values are 2 and 6. Output is [2, 6].
Input
nums = [2, 3, 4, 5, 6, 7]
Output
[1, 8]
Explanation: The array length is 6, so N = 6 + 2 = 8. The expected sequence is [1, 2, 3, 4, 5, 6, 7, 8]. The input is missing the first and last elements. Output is [1, 8].
Input
nums = [1, 2, 3, 5, 6, 7, 8]
Output
[4, 9]
Explanation: The array length is 7, so N = 7 + 2 = 9. The expected sequence is [1, 2, 3, 4, 5, 6, 7, 8, 9]. The input is missing 4 and 9. Output is [4, 9].
Constraints
- 2 <= nums.length <= 10^5
- 1 <= nums[i] <= nums.length + 2
- All elements in nums are distinct
- Exactly two integers are missing from the range [1, nums.length + 2]
Optimal Approach & Strategy
Perform a single pass to compute the sum and sum of squares of the array, then use arithmetic formulas to derive the missing numbers via a quadratic equation. This runs in O(N) time with O(1) extra space.
Brute Force Approach
Iterate from 1 to N and check for each number whether it exists in the array using a linear search; collect the two numbers that are not found. This requires O(N^2) time in the worst case and is impractical for large N.
Verified Code Solutions
function findMissingNumbers(nums) {
let n = nums.length + 2;
let totalSum = (n * (n + 1)) / 2;
let arraySum = nums.reduce((a, b) => a + b, 0);
let missingSum = totalSum - arraySum;
for (let i = 1; i <= n; i++) {
if (!nums.includes(i)) {
let otherMissing = missingSum - i;
if (!nums.includes(otherMissing) && otherMissing <= n) {
return [i, otherMissing];
}
}
}
}class Solution {
public:
vector<int> findMissingNumbers(vector<int>& nums) {
int n = nums.size() + 2;
int totalSum = (n * (n + 1)) / 2;
int arraySum = 0;
for (int num : nums) {
arraySum += num;
}
int missingSum = totalSum - arraySum;
for (int i = 1; i <= n; i++) {
bool found = false;
for (int num : nums) {
if (num == i) {
found = true;
break;
}
}
if (!found) {
int otherMissing = missingSum - i;
bool otherFound = false;
for (int num : nums) {
if (num == otherMissing) {
otherFound = true;
break;
}
}
if (!otherFound && otherMissing <= n) {
return {i, otherMissing};
}
}
}
return {};
}
}class Solution {
public int[] findMissingNumbers(int[] nums) {
int n = nums.length + 2;
int totalSum = (n * (n + 1)) / 2;
int arraySum = 0;
for (int num : nums) {
arraySum += num;
}
int missingSum = totalSum - arraySum;
for (int i = 1; i <= n; i++) {
boolean found = false;
for (int num : nums) {
if (num == i) {
found = true;
break;
}
}
if (!found) {
int otherMissing = missingSum - i;
boolean otherFound = false;
for (int num : nums) {
if (num == otherMissing) {
otherFound = true;
break;
}
}
if (!otherFound && otherMissing <= n) {
return new int[]{i, otherMissing};
}
}
}
return new int[]{};
}
}def find_missing_numbers(nums):
n = len(nums) + 2
total_sum = (n * (n + 1)) // 2
array_sum = sum(nums)
missing_sum = total_sum - array_sum
for i in range(1, n + 1):
if i not in nums:
other_missing = missing_sum - i
if other_missing not in nums and other_missing <= n:
return [i, other_missing]function findMissingNumbers(nums) {
let n = nums.length + 2;
let totalSum = (n * (n + 1)) / 2;
let arraySum = nums.reduce((a, b) => a + b, 0);
let missingSum = totalSum - arraySum;
for (let i = 1; i <= n; i++) {
if (!nums.includes(i)) {
let otherMissing = missingSum - i;
if (!nums.includes(otherMissing) && otherMissing <= n) {
return [i, otherMissing];
}
}
}
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.