Find All Numbers Disappeared in an Array Java Solution

This solution addresses the classic LeetCode problem of finding all numbers that disappeared from an array, requiring clever use of array indexing and in-place modification techniques for optimal performance.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we modify the input array in-place, or must we preserve it?
2. What is the expected range of values in the array? (e.g., 1 to n where n = array length)
3. Are there any constraints on the input size? (e.g., up to 10⁵ elements)
4. Should we return the missing numbers in any specific order?
5. Do we need to handle negative numbers or zero values in the input?

Restatement: Given an array of integers where each integer is in the range [1, n] (where n is the size of the array), find all numbers in that range that do not appear in the array.

Clarification of inputs, outputs, and constraints:

• Input: An array nums of length n where each element is in the range [1, n]
• Output: A list of integers that are missing from the array (in range [1, n])
• Constraints:
  • All elements in the input array are within [1, n]
  • Array size can be up to 10⁵
  • Elements may repeat (duplicates allowed)
• Assumption: We're looking for numbers in the range [1, n] that don't appear in the array

Data shape and hidden structure: The problem presents a permutation-like structure where we have n positions but some numbers from [1, n] are missing. The key insight is that we can use the array indices themselves to mark presence of numbers, since we have exactly n positions and need to track n possible values.

The problem has a hidden constraint that allows us to use the array indices as a hash table - we can map each number to an index and mark that index as "seen" by negating the value there. This is a classic "array as hash table" pattern that enables O(1) space solutions.

2. Pattern Recognition

Identifying the pattern

The most likely pattern here is "Array Index Manipulation" or "Cyclic Sort" variant.

Wording that signals the pattern

• "Find all numbers disappeared in an array" - This suggests we're looking for missing values in a sequence
• "Array of integers" with constraints that numbers are in range [1, n] - This indicates we can leverage array indices as a lookup mechanism
• The problem asks to find missing numbers, which is classic "missing element in sequence" pattern

Why this fits the pattern

The key insight is that we're given an array of size n where each element is in the range [1, n]. This means we can use the array indices (0 to n-1) as a mapping mechanism. If we can mark which numbers from 1 to n have been seen, we can identify the missing ones.

Core insight

Since array indices are 0-based but numbers are 1-based, we can use index = value - 1 to map each number to its corresponding index. By marking visited indices (e.g., by negating the value at that index), we can identify which indices never got marked, meaning their corresponding numbers were missing.

This is a classic "marking" technique where we use the array itself as a hash table to avoid extra space, which is very common in array-based problems where the input domain matches the expected output domain.

3. Approach Evolution

My first instinct is to use a brute force approach where I check for each number from 1 to n whether it exists in the array. But that's O(n²) because for each number I'd have to scan the entire array, and that's inefficient. Let me think about how to optimize this.

I notice that if I can somehow mark the presence of numbers in-place, I might be able to reduce this to O(n) time. The key insight is that since we're dealing with an array of size n containing numbers from 1 to n, I can use the array indices themselves as markers.

The approach that makes sense is to iterate through the array and for each number, mark the index corresponding to that number as negative (or use some other marker). Then I can iterate again and collect all indices that still have positive values, which would indicate missing numbers.

Let me trace through this: if I see number 3, I mark index 2 (since array is 0-indexed) as negative. When I finish, indices with positive values mean their corresponding numbers (index+1) were never seen.

This approach works because:

1. We're guaranteed that numbers are in range [1,n]
2. We can use the array indices as a hash table implicitly
3. We don't need extra space for tracking, making it O(1) space (excluding output)
4. The in-place modification is acceptable since we're told the input can be mutated

The key invariant that must hold is that after processing, any index i has a negative value if and only if the number (i+1) was present in the original array.

This is a clever use of the input array as both data and state tracking, avoiding any additional space usage while maintaining linear time complexity.

4. Data Structure Choice

For this problem, I'll use the input array itself as a marker structure to avoid extra space usage.

Primary Data Structures:

1. Input array (int[] nums) - This is our main data structure that we'll modify in-place to mark presence of numbers
2. Integer variables - For loop counters and temporary storage

Why this choice is optimal:

• Since we're asked to find missing numbers in range [1,n], and the array size is exactly n, we can use the array indices as a hash table
• The key insight is that for any number x in the array, we can mark index x-1 as visited by making that value negative
• This allows us to reuse the input array for our marking logic without requiring additional space

Space considerations:

• We don't use any auxiliary data structures like HashSets or additional arrays
• The space complexity remains O(1) extra space (not counting the input array)
• This is optimal for the follow-up constraint where we're asked to avoid extra space

Helper structures:

• No additional helper data structures needed
• We'll use simple integer arithmetic to map numbers to indices

This approach leverages the constraint that array values are in range [1,n] and the array size is n, making it possible to use the array indices as a hash table for O(1) space complexity.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example Input: [4, 3, 2, 7, 8, 2, 3, 1]

Step 1: Initialize the array and prepare to mark presence

• Array: [4, 3, 2, 7, 8, 2, 3, 1]
• We'll use the array itself to mark presence by negating values at specific indices

Step 2: Process each element and mark its corresponding index

• Element 4 at index 0 → Mark index 3 (value 7) as negative: [4, 3, 2, -7, 8, 2, 3, 1]
• Element 3 at index 1 → Mark index 2 (value 2) as negative: [4, 3, -2, -7, 8, 2, 3, 1]
• Element 2 at index 2 → Mark index 1 (value 3) as negative: [4, -3, -2, -7, 8, 2, 3, 1]
• Element 7 at index 3 → Mark index 6 (value 3) as negative: [4, -3, -2, -7, 8, 2, -3, 1]
• Element 8 at index 4 → Mark index 7 (value 1) as negative: [4, -3, -2, -7, 8, 2, -3, -1]
• Element 2 at index 5 → Index 1 already marked, so skip
• Element 3 at index 6 → Index 2 already marked, so skip
• Element 1 at index 7 → Mark index 0 (value 4) as negative: [-4, -3, -2, -7, 8, 2, -3, -1]

Step 3: Find all positive values and collect missing numbers

• Index 0: value -4 (negative) → skip
• Index 1: value -3 (negative) → skip
• Index 2: value -2 (negative) → skip
• Index 3: value -7 (negative) → skip
• Index 4: value 8 (positive) → missing number is 5
• Index 5: value 2 (positive) → missing number is 6
• Index 6: value -3 (negative) → skip
• Index 7: value -1 (negative) → skip

Final Result: [5, 6]

The key insight is that we can use the array indices themselves as a hash table to mark which numbers are present, avoiding extra space usage. The algorithm correctly identifies that numbers 5 and 6 were never seen in the array, making them the disappeared numbers.

This approach handles all edge cases properly:

• Empty arrays return empty lists
• Single element arrays work correctly
• Duplicates don't affect the marking process since we only mark once per unique number
• The algorithm terminates because each element is processed exactly once

6. Java Solution

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        
        // Mark numbers as visited by negating the value at corresponding index
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        
        // Collect indices that still have positive values
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        
        return result;
    }
}

This solution uses the input array itself as a hash map by marking visited numbers through sign changes. For each number in the array, we mark the element at the corresponding index (value-1) as negative to indicate that number has been seen. Then we collect all indices where values are still positive, which correspond to missing numbers.

The approach is optimal in both time and space complexity while maintaining the constraint that we don't use extra space beyond what's required for the output.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes exactly two passes through the array:

1. First pass: O(n) to mark disappeared numbers by negating values at corresponding indices
2. Second pass: O(n) to collect all positive values and their indices

Since these are sequential operations, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(1)

The solution uses only constant extra space beyond the output array:

• We modify the input array in-place, so no additional arrays are created
• The result list is not counted toward space complexity as it's required output
• No recursion stack or auxiliary data structures are used

Why these bounds are correct:

The O(n) time complexity is optimal for this problem because we must examine each element at least once to determine which numbers are missing. Any algorithm that solves this problem must make at least one pass through all n elements.

The O(1) space complexity is achieved by leveraging the input array itself as a marker. Since we're only asked to return the missing numbers and not reconstruct the original array, we can safely modify the input in-place by using the sign of each element as a flag.

This solution is optimal because:

1. It achieves linear time complexity, which is the best possible for this problem
2. It uses constant space, avoiding any additional memory allocation beyond what's necessary for the output
3. It's a single-pass approach that doesn't require preprocessing or additional data structures

The solution is near-optimal for the constraints of the problem, using the array's own structure to encode information rather than requiring additional space.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Handle gracefully with empty result list
• Single element array: Need to check if value is 1 or not to determine absence

Duplicate Values and Repeated States

• The problem states that each number in the array is in range [1, n] where n = array length
• However, duplicates can exist in the input array, which is valid per problem constraints
• The algorithm must correctly handle arrays with duplicates by only counting unique disappeared numbers

Boundary Conditions

• Array with all elements present: Should return empty list
• Array with no elements present: Should return all numbers from 1 to n
• Array with one element: Need to check if that element is 1 or not

Common Implementation Mistakes

• Index out of bounds: Using nums[i] as index without checking range [1, n]
• Modifying input array: The problem asks for O(1) extra space but doesn't prohibit modifying input
• Incorrect range handling: Confusing 0-based vs 1-based indexing (array indices vs values)
• Missing edge case handling: Not considering arrays with all elements present or missing elements

Implementation-specific Pitfalls

// Common mistake - incorrect indexing:
// This will fail for nums[i] = n+1 or 0
int index = nums[i] - 1; // Should validate that nums[i] is in [1,n]

// Another mistake - not handling negative signs properly:
// If we mark visited by negating, we must preserve original values
// for proper indexing calculations

The key insight is that since the array contains integers from 1 to n, we can use the array indices themselves as a hash map without additional space, but must be careful about maintaining original values for indexing calculations.

9. Alternative Approaches

There are several alternative approaches to solving this problem, each with different trade-offs:

Approach 1: Using HashSet

public List<Integer> findDisappearedNumbers(int[] nums) {
    Set<Integer> numSet = new HashSet<>();
    for (int num : nums) {
        numSet.add(num);
    }
    
    List<Integer> result = new ArrayList<>();
    for (int i = 1; i <= nums.length; i++) {
        if (!numSet.contains(i)) {
            result.add(i);
        }
    }
    return result;
}

This approach uses O(n) extra space for the HashSet and has O(n) time complexity. It's more readable but uses additional memory.

Approach 2: Sorting Approach

public List<Integer> findDisappearedNumbers(int[] nums) {
    Arrays.sort(nums);
    List<Integer> result = new ArrayList<>();
    int expected = 1;
    
    for (int i = 0; i < nums.length; i++) {
        while (expected < nums[i]) {
            result.add(expected);
            expected++;
        }
        expected++;
    }
    
    while (expected <= nums.length) {
        result.add(expected);
        expected++;
    }
    return result;
}

This approach sorts the array first and then scans for missing numbers. It's O(n log n) time complexity due to sorting, which is less efficient than our optimal solution.

Approach 3: Using Extra Array

public List<Integer> findDisappearedNumbers(int[] nums) {
    int[] present = new int[nums.length + 1];
    
    for (int num : nums) {
        present[num] = 1;
    }
    
    List<Integer> result = new ArrayList<>();
    for (int i = 1; i <= nums.length; i++) {
        if (present[i] == 0) {
            result.add(i);
        }
    }
    return result;
}

This approach uses an auxiliary array to mark presence, which is O(n) space but more intuitive than the in-place modification approach.

The key trade-off is between space efficiency and time complexity. Our chosen solution optimizes for O(1) extra space (excluding output) while maintaining O(n) time complexity, making it the most efficient approach for this constraint.

10. Test Cases

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int n = nums.length;
        
        // Mark numbers as visited by negating values at corresponding indices
        for (int i = 0; i < n; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        
        // Collect indices where values are still positive (missing numbers)
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        
        return result;
    }
}

Sample Test Cases

Example 1:

int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
// Expected: [5, 6]
// Numbers 5 and 6 are missing from the range [1,8]

Example 2:

int[] nums = {1, 1};
// Expected: [2]
// Number 2 is missing from the range [1,2]

Tricky Case - All Numbers Present:

int[] nums = {1, 2, 3, 4};
// Expected: []
// All numbers from 1 to 4 are present

Boundary Case - Single Element:

int[] nums = {1};
// Expected: []
// Only number 1 is present, so no missing numbers

Edge Case - Empty Array:

int[] nums = {};
// Expected: []
// No elements to process

Edge Case - Large Range with Missing Numbers:

int[] nums = {2, 2, 2, 2};
// Expected: [1, 3, 4]
// Numbers 1, 3, and 4 are missing from range [1,4]

11. Final Summary

The core insight is to leverage the array indices themselves as a marking mechanism to identify missing numbers without requiring additional space. By negating values at corresponding indices, we can efficiently detect which numbers in the range [1,n] are absent. This approach achieves optimal O(n) time and O(1) space complexity by using the input array as both the data structure and the marker, making it the most efficient solution for this constrainted problem.