Leetcode – Find All Numbers Disappeared in an Array Solution in Python

Spread the love

One of the essential skills for any software engineer or competitive programmer is the ability to solve array-based problems efficiently. In this article, we will discuss one such problem on Leetcode named “Find All Numbers Disappeared in an Array”. We will take an in-depth look at various solutions to this problem using Python and analyze the time and space complexities.

Table of Contents

  1. Problem Statement and Understanding
  2. Approach 1: Using an Additional Array
  3. Approach 2: Modifying the Original Array In-place
  4. Approach 3: Mathematical Approach
  5. Time and Space Complexity Analysis
  6. Comparing the Approaches
  7. Conclusion

1. Problem Statement and Understanding

Problem Statement

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array.

Example:

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

Output: [5,6]

Understanding the Problem

We have an array containing n integers, and each integer is in the range [1, n]. Some elements in the array might appear twice, while others might not appear at all. Our goal is to find the numbers from 1 to n that don’t appear in the array.

2. Approach 1: Using an Additional Array

One way to solve this problem is by using an additional array to keep track of the presence of each number.

def findDisappearedNumbers(nums):
    # Create an array to keep track of the presence of each number
    presence = [0] * (len(nums) + 1)
    
    # Mark the numbers that are present
    for num in nums:
        presence[num] = 1
        
    # Find the numbers that are not present
    result = []
    for i in range(1, len(presence)):
        if presence[i] == 0:
            result.append(i)
    
    return result

3. Approach 2: Modifying the Original Array In-place

We can solve this problem more efficiently by modifying the original array in-place. This approach takes advantage of the fact that the array indices are also in the range [1, n].

def findDisappearedNumbers(nums):
    # Mark the numbers that are present
    for num in nums:
        index = abs(num) - 1
        nums[index] = -abs(nums[index])
        
    # Find the indices that are positive, which means the number is not present
    result = []
    for i, num in enumerate(nums):
        if num > 0:
            result.append(i + 1)
    
    return result

4. Approach 3: Mathematical Approach

This approach involves using sets. We can create a set of numbers from 1 to n and subtract the set of numbers present in the array.

def findDisappearedNumbers(nums):
    # Create sets and find the difference
    return list(set(range(1, len(nums) + 1)) - set(nums))

5. Time and Space Complexity Analysis

  • Approach 1: This approach has a time complexity of O(n) but uses an additional array, giving it a space complexity of O(n).
  • Approach 2: This approach also has a time complexity of O(n), but it uses O(1) additional space since it modifies the original array in-place.
  • Approach 3: This approach has a time complexity of O(n) but uses additional space to create sets, giving it a space complexity of O(n).

6. Comparing the Approaches

Approach 2 is the most space-efficient as it doesn’t use any additional data structures. However, it modifies the original array, which might not be desirable in all scenarios.

Approach 1 and Approach 3 are similar in terms of space complexity, but Approach 3 is more concise.

7. Conclusion

In this article, we explored three different approaches to solving the “Find All Numbers Disappeared in an Array” problem on Leetcode using Python. Understanding various approaches to solve a problem is crucial as it helps in improving problem-solving skills and understanding trade-offs between different solutions.

The in-place modification approach is efficient in terms of space complexity, while the mathematical approach using sets is more elegant. Depending on the constraints and requirements of your application, you may choose the approach that best fits your needs.

Leave a Reply