LeetCode 448: Find All Numbers Disappeared in an Array Solution

Master LeetCode problem 448 (Find All Numbers Disappeared in an Array), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

448. Find All Numbers Disappeared in an Array

Easy

Array Hash Table

Problem Explanation

Explanation

To solve this problem without using extra space and in O(n) runtime, we can iterate through the input array nums and mark the elements that we have seen by negating the value at the index corresponding to the absolute value of the element. After the marking step, any positive value remaining in the array indicates an element that did not appear in the input array.

Algorithmic Idea

Iterate through the input array nums.
For each element num, mark the element at index abs(num) - 1 by negating its value.
After marking, any positive value in the array at index i indicates that i + 1 did not appear in the input array.

Time Complexity

The time complexity of this approach is O(n) where n is the number of elements in the input array.

Space Complexity

The approach does not use any extra space, so the space complexity is O(1).

Solution Code

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 448 (Find All Numbers Disappeared in an Array)?

This page provides optimized solutions for LeetCode problem 448 (Find All Numbers Disappeared in an Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 448 (Find All Numbers Disappeared in an Array)?

The time complexity for LeetCode 448 (Find All Numbers Disappeared in an Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 448 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 448 in Java, C++, or Python.

Back to LeetCode Solutions