Skip to main content

448. Find All Numbers Disappeared in an Array

easyAsked at Duolingo

Identify which values from 1–n are absent in an array of n integers — the same gap-detection logic Duolingo's streak-repair system uses to spot which daily XP records are missing from a learner's history without a second data structure.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Constraints

  • n == nums.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n

Examples

Example 1

Input
nums = [4,3,2,7,8,2,3,1]
Output
[5,6]

Explanation: Values 5 and 6 are absent from the array.

Example 2

Input
nums = [1,1]
Output
[2]

Approaches

1. Brute force — hash set

Store all present values in a Set, then collect every integer from 1 to n that is not in the Set.

Time
O(n)
Space
O(n)
function findDisappearedNumbers(nums) {
  const seen = new Set(nums);
  const result = [];
  for (let i = 1; i <= nums.length; i++) {
    if (!seen.has(i)) result.push(i);
  }
  return result;
}

Tradeoff:

2. Optimal — index negation (O(1) extra space)

Use sign flipping in-place: for each value v, negate nums[v-1] to mark v as seen, then collect indices whose value remains positive.

Time
O(n)
Space
O(1)
function findDisappearedNumbers(nums) {
  for (let i = 0; i < nums.length; i++) {
    const idx = Math.abs(nums[i]) - 1;
    if (nums[idx] > 0) nums[idx] = -nums[idx];
  }
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) result.push(i + 1);
  }
  return result;
}

Tradeoff:

Duolingo-specific tips

Duolingo's interviewers care about the follow-up constraint: can you solve it without allocating extra memory? The in-place sign-flip trick is the expected answer. Walk through why abs() is needed on the second read — interviewers want to see you reason about already-negated slots. This maps directly to how Duolingo's backend would audit a compressed activity log for missing day-entries without loading a second buffer.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find All Numbers Disappeared in an Array and other Duolingo interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →