Find Missing Indices — Problem Statement & Solution Guide
Problem Description
Given a positive integer n and an array of distinct integers arr, find all indices from 1 to n that are not present in arr.
Examples
Input
n = 5, arr = [4, 3, 2, 7, 8, 1]
Output
[5]
Explanation: Step-by-step: First, remove duplicates from the array to get [4, 3, 2, 7, 8, 1]. Then, find the missing indices from 1 to n. In this case, the missing index is 5 because the numbers 1 to 4 and 6 to n are either present or out of range.
Input
n = 10, arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output
[]
Explanation: Step-by-step: The array already contains all indices from 1 to n, so there are no missing indices.
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= n
Optimal Approach & Strategy
Iterate array, use absolute value as index and negate the value at that index. In second pass, any positive value's index + 1 is a missing number. Time O(N), Space O(1).
Brute Force Approach
Use a HashSet to store elements, then loop 1 to N. Space O(N).
Verified Code Solutions
function findMissingIndices(n, arr) {
// Remove duplicates from the array
let uniqueArr = [...new Set(arr)];
let missingIndices = [];
for (let i = 1; i <= n; i++) {
if (!uniqueArr.includes(i)) {
missingIndices.push(i);
}
}
return missingIndices;
}class Solution {
public:
vector<int> findMissingIndices(int n, vector<int>& arr) {
// Remove duplicates from the array
unordered_set<int> uniqueArr(arr.begin(), arr.end());
vector<int> missingIndices;
for (int i = 1; i <= n; i++) {
if (uniqueArr.find(i) == uniqueArr.end()) {
missingIndices.push_back(i);
}
}
return missingIndices;
}
}import java.util.*;
class Solution {
public List<Integer> findMissingIndices(int n, int[] arr) {
// Remove duplicates from the array
Set<Integer> uniqueArr = new HashSet<>();
for (int num : arr) {
uniqueArr.add(num);
}
List<Integer> missingIndices = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!uniqueArr.contains(i)) {
missingIndices.add(i);
}
}
return missingIndices;
}
}def find_missing_indices(n, arr):
# Remove duplicates from the array
unique_arr = list(set(arr))
missing_indices = [i for i in range(1, n+1) if i not in unique_arr]
return missing_indicesfunction findMissingIndices(n, arr) {
// Remove duplicates from the array
let uniqueArr = [...new Set(arr)];
let missingIndices = [];
for (let i = 1; i <= n; i++) {
if (!uniqueArr.includes(i)) {
missingIndices.push(i);
}
}
return missingIndices;
}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.