LeetCode: Find All Numbers Disappeared in an Array — Optimal Solution Deeply Explained

LeetCode: Find All Numbers Disappeared in an Array — Optimal Solution Deeply Explained

Table of Content

• Introduction
• Intuition/Solution
• Step-by-Step Visual Guide
• Implementation Code

Introduction

We often come across problems that require us to think outside the box and come up with innovative solutions. One such intriguing problem is “Find All Numbers Disappeared in an Array,” where the goal is to find the missing numbers in a given array of integers.

We will delve deep into the problem, exploring the intuition behind a clever solution that doesn’t rely on additional data structures. We’ll demonstrate how to use the input array itself as a tool to mark the presence of numbers and, ultimately, identify the missing ones.

This technique not only saves memory but also showcases an elegant solution with time complexity of O(n) and space complexity of O(1)

Intuition/Solution

At first you may be prompted to want to use a Hash Table or some sort of data structure to save all the numbers we’ve encountered. However, there’s a better solution.

The intuition behind the solution to the “Find All Numbers Disappeared in an Array” problem is to use the given array itself as a data structure to store the information about the presence of numbers in the range 1 to n. Since the given array is of length n, it can accommodate all the numbers from 1 to n.

The key insight is that each number in the array can be used to mark another number’s presence, since each value in the array should be in the range of 1 to n. This is done by using the absolute value of the current number as an index and negating the number at that index. By doing so, we can track the presence of the numbers without using any additional data structures.

Here’s a Visual

Original array: [4, 3, 2, 7, 8, 2, 3, 1]

Marked array:  [-4, -3, -2, -7,  8,  2, -3, -1]
Index:          1   2   3   4   5   6   7   8

Positive nums:                  5   6

The negative sign indicates that the number corresponding to the index has been encountered in the array. For example, if nums[2] is negative, it indicates that the number 3 (since the index is 0-based) has been encountered in the array.

Step-by-Step Visual Guide

Given an array: [4, 3, 2, 7, 8, 2, 3, 1], n = 8, and the numbers in the range 1 to n are [1, 2, 3, 4, 5, 6, 7, 8].

Step 1
Iterate through the array and mark numbers at positions (abs(nums[i]) — 1) as negative.

1.1. Start with the first number in the array, 4:

Original array: [4, 3, 2, 7, 8, 2, 3, 1]

Mark position:  [ ,  ,  , -7,  ,  ,  ,  ] (mark position 3)

1.2. Continue with the second number, 3:

Original array: [4, 3, 2, 7, 8, 2, 3, 1]

Mark position:  [ ,  , -2, -7,  ,  ,  ,  ] (mark position 2)

1.3. Keep iterating through the array:

Original array: [4, 3, 2, 7, 8, 2, 3, 1]

Mark position:  [-4, -3, -2, -7,  ,  ,  ,  ] (mark positions 0 and 1)

Mark position:  [-4, -3, -2, -7, 8, 2, -3, -1] (mark positions 6 and 7)

Unmarked positions: 5 and 6

Step 2
Iterate through the marked array and add (index + 1) to the result array for each positive number.

2.1. Start with the first number in the marked array, -4:

Marked array:  [-4, -3, -2, -7,  8,  2, -3, -1]
Index:           1   2   3   4   5   6   7   8

Since -4 is negative, skip.

2.2. Continue iterating through the marked array:

Marked array:  [-4, -3, -2, -7,  8,  2, -3, -1]
Index:           1   2   3   4   5   6   7   8

Since -3, -2, -7, -3, and -1 are negative, skip them.

2.3. When we reach the positive numbers, 8 and 2:

Marked array:  [-4, -3, -2, -7,  8,  2, -3, -1]
Index:           1   2   3   4   5   6   7   8

Positive nums:                   5   6

Result: [5, 6] (missing numbers)

Implementation Code

Python

def findDisappearedNumbers(nums):
    for i in range(len(nums)):
        index = abs(nums[i]) - 1
        nums[index] = -abs(nums[index])

    result = []
    for i in range(len(nums)):
        if nums[i] > 0:
            result.append(i + 1)

    return result

Javascript

var findDisappearedNumbers = function(nums){
    const result = [];

    // the first loop is to mark down the numbers 
    for (let i = 0; i < nums.length; i++){
        const index = Math.abs(nums[i]) - 1;
        nums[index] = Math.abs(nums[index]) * -1;
    }

    // the second loop is the find all the positive numbers
    for (let i = 0; i < nums.length; i++){
        if (nums[i] > 0) result.push(i+1)
    }

    return result
}