DEV Community

Cover image for 448. Find All Numbers Disappeared in an Array
Harsh Rajpal
Harsh Rajpal

Posted on

448. Find All Numbers Disappeared in an Array

Problem Statement:
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.

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

Example 2:

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

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

Solution:
Algorithm:

  1. Create a HashSet
  2. Create a List
  3. Add all the elements of the array to the HashSet
  4. Iterate from 1 to the length of the array
  5. If the HashSet does not contain the number, add it to the List
  6. Return the List

Code:

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        HashSet<Integer> hs = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            hs.add(nums[i]);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (!hs.contains(i)) {
                result.add(i);
            }
        }
    }

}
Enter fullscreen mode Exit fullscreen mode

Time Complexity:
O(n)
Space Complexity:
O(n)

Top comments (0)