Given an array nums of n integers where each integer is in the range [1, n], return an array of all the integers that do not appear in the array, sorted in ascending order.
Table of Contents
Sample Input and Expected Output:
Input:
nums = [4, 3, 2, 7, 8, 2, 1, 1]
Output:
Numbers disappeared from the array: [5, 6]
Input:
nums = [3, 3, 2, 4, 6, 2, 5, 1]
Output:
Numbers disappeared from the array: [7, 8]
Solution in C++:
The idea is to use the array itself as a hash table. For each number x in the array, we consider its absolute value abs(x) as the index and negate the value at that index. After processing all numbers, the positions with positive values indicate that the corresponding numbers did not appear in the array. We add those missing numbers to the result array.
#include <iostream>
#include <vector>
#include <cmath>
std::vector<int> findDisappearedNumbers(std::vector<int>& nums) {
std::vector<int> result;
for (int num : nums) {
int index = std::abs(num) - 1; // Convert num to index (zero-based).
if (nums[index] > 0) {
nums[index] = -nums[index]; // Negate the value at index.
}
}
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) {
result.push_back(i + 1); // If the value at index is positive, it's a missing number.
}
}
return result;
}
int main() {
std::vector<int> nums1 = {4, 3, 2, 7, 8, 2, 1, 1};
std::vector<int> nums2 = {3, 3, 2, 4, 6, 2, 5, 1};
std::vector<int> result1 = findDisappearedNumbers(nums1);
std::vector<int> result2 = findDisappearedNumbers(nums2);
std::cout << "Numbers disappeared from the array: [";
for (int num : result1) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
std::cout << "Numbers disappeared from the array: [";
for (int num : result2) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(n), where n is the size of the input vector nums. Each number is processed once in the array.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The algorithm is performed in-place without using any extra data structures, except for the result array, which contains missing numbers and its size is at most n in the worst case.