Practice/Amazon/Leetcode 448. Find All Numbers Disappeared in an Array

Leetcode 448. Find All Numbers Disappeared in an Array

CodingMust

Problem

You are given an array nums containing n integers where each integer falls within the range [1, n] inclusive. Some numbers in this range may appear multiple times in the array, while others may not appear at all.

Your task is to identify and return a list of all integers in the range [1, n] that do not appear in the array.

Requirements

1. Return all missing integers in any order
2. Solve the problem in O(n) time complexity
3. Use only O(1) extra space (not counting the output array)
4. You may modify the input array if needed

Constraints

• n == nums.length
• 1 ≤ n ≤ 100,000
• 1 ≤ nums[i] ≤ n

Examples

Example 1:

Input: nums = [4, 3, 2, 7, 8, 2, 3, 1] Output: [5, 6] Explanation: The array has 8 elements, so we expect numbers 1 through 8. Looking at what's present: 1, 2, 2, 3, 3, 4, 7, 8 The numbers 5 and 6 are missing from this range.

Example 2:

Input: nums = [1, 1] Output: [2] Explanation: Array length is 2, so the valid range is [1, 2]. Only 1 appears (twice), so 2 is missing.

Example 3:

Input: nums = [1, 2, 3, 4, 5] Output: [] Explanation: All numbers from 1 to 5 are present, so nothing is missing.