Review the fundamentals: Arrays guide and time complexities.
Find Missing Indices — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Find Missing Indices problem optimally.
O(n)O(1)Problem Description
Given a positive integer n and an array arr containing distinct integers, each integer lies in the range [1, n]. Your task is to identify every integer i such that 1 ≤ i ≤ n and i does not appear in arr. Return the missing integers sorted in increasing order.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Find Missing Indices"
WHY DOES IT MATTER?
The flag‑by‑index pattern is fundamental for any problem that asks for missing or duplicate elements within a bounded integer domain, enabling linear scans without costly hash structures.
OPTIMIZATION CHALLENGE
The key insight is that the value itself can serve as an address to a flag, turning the array into a bitmap of presence, which collapses two nested loops into a single pass.
REAL-WORLD CONNECTION
Think of a warehouse with n slots; each incoming item places a marker in its slot. Scanning the warehouse once reveals empty slots—analogous to missing indices—without walking each aisle multiple times.
During an interview, first state the O(n) flag‑by‑index idea, then discuss trade‑offs: if mutating the input is disallowed, fall back to a boolean vector; otherwise, use in‑place sign‑flipping for O(1) extra space.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to identifying the complement set of a given subset within the universal range [1,n]. A naive scan for each number in the range against the array leads to O(n·m) time, which is prohibitive when n and the array length m approach 10⁵ or higher. The optimal paradigm leverages constant‑time membership checks by either using an auxiliary boolean/bitset of size n (O(n) space) or by in‑place marking via index‑based swapping, achieving linear time O(n) while keeping extra space to O(1) when mutation of the input is allowed. This approach is a classic example of the "bucket/flag" pattern, where the index itself encodes presence information, eliminating the need for nested loops or expensive look‑ups.
Interview Questions on This Problem
Q1How would you find all missing numbers if the array could contain duplicates as well as numbers outside the [1,n] range?
First filter out-of-range values and clamp duplicates by marking visited indices (e.g., set arr[abs(num)-1] to negative). Then iterate 1..n and collect indices whose values remain positive, which represent missing numbers.
Q2Can you solve the problem in O(1) extra space without modifying the original array?
No, because without extra storage or mutation you cannot record which indices have been seen; the lower bound for deterministic linear‑time solutions requires either O(n) auxiliary bits or in‑place modifications.
Q3Explain how the "sum and sum‑of‑squares" technique can be used when exactly two numbers are missing.
Compute the expected sum S=n(n+1)/2 and sum of squares Q=n(n+1)(2n+1)/6, subtract the actual sum s and sum of squares q from the array, yielding equations (x+y)=S‑s and (x²+y²)=Q‑q. Solve the system to obtain the two missing values.
Examples
Input
5 [2,3,1]
Output
[4,5]
Explanation: The numbers from 1 to 5 are {1,2,3,4,5}. The array provides {2,3,1}. Removing these leaves {4,5}, which are returned in ascending order.
Input
8 [8,5,2,1,7]
Output
[3,4,6]
Explanation: All numbers 1‑8 are {1,2,3,4,5,6,7,8}. The array contains {8,5,2,1,7}. The absent numbers are 3, 4 and 6; they are output sorted.
Input
3 []
Output
[1,2,3]
Explanation: The array is empty, so none of the indices 1,2,3 appear. All three indices are missing and are returned in order.
Constraints
- 1 ≤ n ≤ 10⁵
- 0 ≤ arr.length ≤ n
- All elements in arr are distinct
- 1 ≤ arr[i] ≤ n
Optimal Approach & Strategy
Create a boolean presence array of size n (or flip signs in‑place) while iterating once, then iterate 1..n to output indices that remain false/positive; both steps are O(n).
Brute Force Approach
For each i from 1 to n, scan the entire array to see if i appears, collecting those that don’t; this is O(n·m) time.
Code Solutions
function findMissingIndices(n, arr) {
const present = new Array(n + 1).fill(false);
for (const num of arr) {
if (num >= 1 && num <= n) {
present[num] = true;
}
}
const result = [];
for (let i = 1; i <= n; i++) {
if (!present[i]) {
result.push(i);
}
}
return result;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
rl.on('line', line => {
lines.push(line);
if (lines.length === 2) {
const n = parseInt(lines[0]);
const arr = lines[1].split(' ').map(Number);
const result = findMissingIndices(n, arr);
console.log(result.join(' '));
rl.close();
}
});#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> findMissingIndices(int n, vector<int>& arr) {
vector<int> present(n + 1, 0);
for (int num : arr) {
if (num >= 1 && num <= n) {
present[num] = 1;
}
}
vector<int> result;
for (int i = 1; i <= n; i++) {
if (present[i] == 0) {
result.push_back(i);
}
}
return result;
}
int main() {
int n;
if (!(cin >> n)) return 0;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
vector<int> result = findMissingIndices(n, arr);
for (int i = 0; i < result.size(); i++) {
if (i > 0) cout << " ";
cout << result[i];
}
cout << endl;
return 0;
}import java.util.*;
import java.io.*;
public class Main {
public static int[] findMissingIndices(int n, int[] arr) {
boolean[] present = new boolean[n + 1];
for (int num : arr) {
if (num >= 1 && num <= n) {
present[num] = true;
}
}
List<Integer> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (!present[i]) {
result.add(i);
}
}
int[] res = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
res[i] = result.get(i);
}
return res;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.trim().isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] arr = new int[n];
String arrLine = br.readLine();
if (arrLine != null && !arrLine.trim().isEmpty()) {
String[] parts = arrLine.trim().split("\\s+");
for (int i = 0; i < n && i < parts.length; i++) {
arr[i] = Integer.parseInt(parts[i]);
}
}
int[] result = findMissingIndices(n, arr);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < result.length; i++) {
if (i > 0) sb.append(" ");
sb.append(result[i]);
}
System.out.println(sb.toString());
}
}def find_missing_indices(n: int, arr: list) -> list:
present = [False] * (n + 1)
for num in arr:
if 1 <= num <= n:
present[num] = True
result = []
for i in range(1, n + 1):
if not present[i]:
result.append(i)
return result
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().split()
if not data:
sys.exit(0)
n = int(data[0])
arr = list(map(int, data[1:1+n]))
result = find_missing_indices(n, arr)
print(' '.join(map(str, result)))function findMissingIndices(n, arr) {
const present = new Array(n + 1).fill(false);
for (const num of arr) {
if (num >= 1 && num <= n) {
present[num] = true;
}
}
const result = [];
for (let i = 1; i <= n; i++) {
if (!present[i]) {
result.push(i);
}
}
return result;
}
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
rl.on('line', line => {
lines.push(line);
if (lines.length === 2) {
const n = parseInt(lines[0]);
const arr = lines[1].split(' ').map(Number);
const result = findMissingIndices(n, arr);
console.log(result.join(' '));
rl.close();
}
});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.