Given an array nums with distinct integers in the range [0, n]. This array represents a permutation of the integers from 0 to n with one element missing. Find the missing element in the array.
Example 1
Input: nums = [3, 0, 1]
Output: 2
Explanation: The array has length 3, so every value must belong to [0, 3]. The values 0, 1, and 3 are present, leaving 2 as the missing value.
Example 2
Input: nums = [0, 1]
Output: 2
Explanation: The array has length 2, so the expected range is [0, 2]. Both 0 and 1 occur in the array, so the upper boundary value 2 is missing.
Brute Force Approach
Check every value from 0 to n in the array. If a value is present, move to the next one. The first value that cannot be found is the missing number.
The same array may be scanned for every possible value. This repeated work makes the approach slow for large inputs, but it clearly shows the basic condition that must be checked.
Algorithm
Consider every possible value in the complete range from
0to the array length.Search the entire array for the current value.
Stop the inner search as soon as a match is found, because no more checking is needed for that value.
If a value is not found after the scan, return it immediately as the missing number.
The search ends no later than the upper boundary of the range. For an empty array,
0is returned naturally.
Dry Run
Missing Number Brute Force
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the missing element. int missingNumber(vector<int>& nums) { int n = nums.size(); // Every number from 0 through n is a possible missing value. for (int candidate = 0; candidate <= n; candidate++) { bool found = false; // Search for the current candidate and stop once it is found. for (int value : nums) { // A match confirms that the candidate is present. if (value == candidate) { found = true; break; } } // The first absent candidate is the unique missing number. if (!found) { return candidate; } } return -1; }};// Driver codeint main() { vector<int> nums = {3, 0, 1}; // instance for class Solution Solution sol; cout << sol.missingNumber(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n²). Up to n + 1 candidates are checked, and each check may inspect all n array elements.
Space Complexity: O(1). Only the candidate and a few control variables are stored, independent of the input size.
Better Approach
The array should contain every integer from 0 to n exactly once, except for the missing number. Since the array has n elements, its indices range from 0 to n - 1.
After sorting, each value should match its index until the missing number is reached. The first index that does not match its value is the missing number. If every index from 0 to n - 1 matches, then n is missing.
Algorithm
Sort the array in increasing order.
Scan the sorted values from the first position to the last.
Compare each value with the index where it should appear.
Return the first index whose value does not match it.
If every position matches, return the array length. This also returns
0correctly for an empty array.
Dry Run
sorting approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the missing element. int missingNumber(vector<int>& nums) { // Ordering makes the expected value at each index explicit. sort(nums.begin(), nums.end()); // The first mismatching index is the missing value. for (int i = 0; i < nums.size(); i++) { // A mismatch identifies the missing value. if (nums[i] != i) { return i; } } // If all positions match, only the upper boundary is absent. return nums.size(); }};// Driver codeint main() { vector<int> nums = {3, 0, 1}; // instance for class Solution Solution sol; cout << sol.missingNumber(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n log n). Sorting dominates the following O(n) scan.
Space Complexity: O(1) because no extra space is used.
Optimal Approach 1
Sorting is not required when every value lies in a small, known range. Since each element is between 0 and n, it can be used directly as an index in a Boolean frequency array.
Mark every value that appears, then scan the frequency array from 0 to n. The first unmarked index is the missing number. A range up to 10⁵ is small enough for this direct-address array to be practical.
Algorithm
Create a Boolean frequency array of size
n + 1, initially markedfalse.Traverse the input and mark the position corresponding to each value as
true.Scan the complete range from
0throughnafter all values have been marked.Return the first index that is still
false, because that value never appeared in the input.The scan ends by index
n. For an empty input, the only position is0, so0is returned.
Dry Run
hash array
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the missing element. int missingNumber(vector<int>& nums) { vector<bool> present(nums.size() + 1, false); // Record every value that appears in the input. for (int value : nums) { present[value] = true; } // The first unmarked index is the missing value. for (int value = 0; value <= nums.size(); value++) { // An unmarked position represents the missing value. if (!present[value]) { return value; } } return -1; }};// Driver codeint main() { vector<int> nums = {3, 0, 1}; // instance for class Solution Solution sol; cout << sol.missingNumber(nums) << '\n'; return 0;}Complexity Analysis:
Time Complexity: O(n), because the input and the n + 1 frequency positions are each scanned once.
Space Complexity: O(n), because a Boolean frequency array of size n + 1 is created.
Optimal Approach 2
The array should contain every integer from 0 to n. Therefore, the expected sum is n × (n + 1) / 2.
The actual sum is found by adding all values present in the array. Since exactly one value is missing, the difference between the expected sum and the actual sum is the missing element.
Algorithm
Compute the sum expected for the complete range
0throughn.Traverse the array once and add all present values.
Subtract the present total from the expected total.
Return the difference, which is the only missing value.
Use a wider integer type where needed. Empty input and missing boundary values require no special case.
Dry Run
sum
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the missing element. int missingNumber(vector<int>& nums) { long long n = nums.size(); // A wide type protects the multiplication and accumulated sum. long long expectedSum = n * (n + 1) / 2; long long actualSum = 0; // Combine all present values so their contribution can be removed. for (int value : nums) { actualSum += value; } return expectedSum - actualSum; }};// Driver codeint main() { vector<int> nums = {3, 0, 1}; // instance for class Solution Solution sol; cout << sol.missingNumber(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n). The formula is evaluated in constant time, and each of the n array values is processed once.
Space Complexity: O(1). Only a fixed number of numeric variables is used, regardless of the input size.
Optimal Approach 3
Every number should appear twice when the complete range and the given array are considered together: once as an expected value and once as an array value. The missing number is the only value that appears once because it has no matching value in the array.
XOR removes matching pairs, and the order of the values does not matter. Therefore, all present numbers cancel and only the missing number remains.
Algorithm
Begin with the upper boundary so the complete expected range is represented.
Traverse the array once, pairing every index with the value at that position through XOR.
Equal expected and present values cancel, regardless of their order.
Return the value that remains after all pairs have canceled.
Empty input returns
0naturally. In JavaScript, ordinary bitwise operations are limited to signed 32-bit integers.
Dry Run
Missing number
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the missing element. int missingNumber(vector<int>& nums) { // Starting with n includes the only expected value not represented by an index. int xorResult = nums.size(); // Pair every index with every present value through XOR. for (int i = 0; i < nums.size(); i++) { xorResult ^= i; xorResult ^= nums[i]; } return xorResult; }};// Driver codeint main() { vector<int> nums = {3, 0, 1}; // instance for class Solution Solution sol; cout << sol.missingNumber(nums) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(n). Each array element and its corresponding index are processed once.
Space Complexity: O(1). The result is accumulated in one integer, with no data structure whose size depends on n.
FAQs
1. Which approach is usually preferred in an interview?
The XOR approach is an excellent final answer because it provides O(n) time, O(1) auxiliary space, and no arithmetic-sum overflow. The sum approach is equally optimal under standard complexity analysis and is often easier to explain. A strong interview response may present the sum idea first and then mention XOR as the overflow-safe alternative.
2. Why does XOR cancellation work regardless of input order?
XOR is commutative and associative, so operands may be rearranged without changing the result. Every present value can therefore be paired with the identical expected value. Each pair becomes zero, regardless of where the array value originally appeared.
3. Why is a wider type needed for the sum approach?
The product n × (n + 1) may exceed a 32-bit integer's maximum value before division occurs. In C++, long long is used, and in Java, at least one operand is converted to long before multiplication. Python integers grow automatically. JavaScript Number is exact for integers only up to 253 - 1 although the stated LeetCode constraints are safely below that limit.
4. Do these approaches still work if duplicate values are allowed?
Not under the same reasoning. A duplicate can replace a missing value and break the one-to-one cancellation assumed by both sum and XOR. The problem would then require different guarantees and often a frequency table, a set with validation, cyclic placement, or another duplicate-aware technique.
Be the first to add a comment.