Welcome to Subscribe On Youtube

448. Find All Numbers Disappeared in an Array

Description

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

 

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Solutions

Solution 1: Set

We can use an array or hash table to record the numbers in the array, and then iterate through the numbers in the [1, n] interval. If the number does not exist in the array or hash table, it means that the number is missing from the array and adds it to the result list.

Time complexity $O(n)$, space complexity $O(n)$. Where $n$ is the array length.

Solution 2

We can traverse the array $nums$ and mark the number at the $

nums[i]

-1$ position as a negative number, indicating that the array $nums[i]$ has appeared. Finally, traverse the array $nums$. If $nums[i]$ is a positive number, it means $i+1$ is missing from the array and add it to the result list.

After the traversal is completed, just return the result list.

Time complexity $O(n)$, space complexity $O(1)$. Where $n$ is the array length.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public List<Integer> findDisappearedNumbers(int[] nums) {
          int n = nums.length;
          for (int x : nums) {
              int i = Math.abs(x) - 1;
              if (nums[i] > 0) {
                  nums[i] *= -1;
              }
          }
          List<Integer> ans = new ArrayList<>();
          for (int i = 0; i < n; i++) {
              if (nums[i] > 0) {
                  ans.add(i + 1);
              }
          }
          return ans;
      }
  }
  
  
  // Solution 2
  class Solution {
      public List<Integer> findDisappearedNumbers(int[] nums) {
          int n = nums.length;
          for (int x : nums) {
              int i = Math.abs(x) - 1;
              if (nums[i] > 0) {
                  nums[i] *= -1;
              }
          }
          List<Integer> ans = new ArrayList<>();
          for (int i = 0; i < n; i++) {
              if (nums[i] > 0) {
                  ans.add(i + 1);
              }
          }
          return ans;
      }
  }
  
  

• class Solution {
  public:
      vector<int> findDisappearedNumbers(vector<int>& nums) {
          int n = nums.size();
          for (int& x : nums) {
              int i = abs(x) - 1;
              if (nums[i] > 0) {
                  nums[i] = -nums[i];
              }
          }
          vector<int> ans;
          for (int i = 0; i < n; ++i) {
              if (nums[i] > 0) {
                  ans.push_back(i + 1);
              }
          }
          return ans;
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      vector<int> findDisappearedNumbers(vector<int>& nums) {
          int n = nums.size();
          for (int& x : nums) {
              int i = abs(x) - 1;
              if (nums[i] > 0) {
                  nums[i] = -nums[i];
              }
          }
          vector<int> ans;
          for (int i = 0; i < n; ++i) {
              if (nums[i] > 0) {
                  ans.push_back(i + 1);
              }
          }
          return ans;
      }
  };
  
  

• class Solution:
      def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
          for x in nums:
              i = abs(x) - 1
              if nums[i] > 0:
                  nums[i] *= -1
          return [i + 1 for i in range(len(nums)) if nums[i] > 0]
  
  
  # Solution 2
  class Solution:
      def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
          for x in nums:
              i = abs(x) - 1
              if nums[i] > 0:
                  nums[i] *= -1
          return [i + 1 for i in range(len(nums)) if nums[i] > 0]
  
  

• func findDisappearedNumbers(nums []int) (ans []int) {
  	n := len(nums)
  	for _, x := range nums {
  		i := abs(x) - 1
  		if nums[i] > 0 {
  			nums[i] = -nums[i]
  		}
  	}
  	for i := 0; i < n; i++ {
  		if nums[i] > 0 {
  			ans = append(ans, i+1)
  		}
  	}
  	return
  }
  
  func abs(x int) int {
  	if x < 0 {
  		return -x
  	}
  	return x
  }
  
  
  // Solution 2
  func findDisappearedNumbers(nums []int) (ans []int) {
  	n := len(nums)
  	for _, x := range nums {
  		i := abs(x) - 1
  		if nums[i] > 0 {
  			nums[i] = -nums[i]
  		}
  	}
  	for i := 0; i < n; i++ {
  		if nums[i] > 0 {
  			ans = append(ans, i+1)
  		}
  	}
  	return
  }
  
  func abs(x int) int {
  	if x < 0 {
  		return -x
  	}
  	return x
  }
  
  

• function findDisappearedNumbers(nums: number[]): number[] {
      const n = nums.length;
      for (const x of nums) {
          const i = Math.abs(x) - 1;
          if (nums[i] > 0) {
              nums[i] *= -1;
          }
      }
      const ans: number[] = [];
      for (let i = 0; i < n; ++i) {
          if (nums[i] > 0) {
              ans.push(i + 1);
          }
      }
      return ans;
  }
  
  
  // Solution 2
  function findDisappearedNumbers(nums: number[]): number[] {
      const n = nums.length;
      for (const x of nums) {
          const i = Math.abs(x) - 1;
          if (nums[i] > 0) {
              nums[i] *= -1;
          }
      }
      const ans: number[] = [];
      for (let i = 0; i < n; ++i) {
          if (nums[i] > 0) {
              ans.push(i + 1);
          }
      }
      return ans;
  }
  
  

All Problems

All Solutions