CODEWITHSUNDEEP
arraysalgorithm
user10100511
user10100511

Reputation:

LeetCode Find All Numbers Disappeared in an Array Question

The problem I am doing is stated as follows:

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.

I found a solution that takes O(n) space fairly quickly however this problem has a condition to find a constant space solution and I do not understand the solution that is given. The constant space solution is recreated here as follows:

    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
                
        # Iterate over each of the elements in the original array
        for i in range(len(nums)):
            
            # Treat the value as the new index
            new_index = abs(nums[i]) - 1
            
            # Check the magnitude of value at this new index
            # If the magnitude is positive, make it negative 
            # thus indicating that the number nums[i] has 
            # appeared or has been visited.
            if nums[new_index] > 0:
                nums[new_index] *= -1
        
        # Response array that would contain the missing numbers
        result = []    
        
        # Iterate over the numbers from 1 to N and add all those
        # that have positive magnitude in the array 
        for i in range(1, len(nums) + 1):
            if nums[i - 1] > 0:
                result.append(i)       
        return result

I don't understand how this code works. To me it seems that every element will be made negative in the first pass and therefore no values will be appended to the answer list. I ran it through a debugger and it seems that is not what is happening. I was hoping that someone can explain to me what it is doing.

Upvotes: 3

Views: 3018

Answers (1)

Yash Shah
Yash Shah

Reputation: 1654

Let's take an example:

nums = [4,3,2,7,8,2,3,1]

Now Let's iterate over it,

Index-1: Value = 4 -> Mark (Value - 1) -> (4-1) index element as negative provided that element is positive.

Now, nums = [4,3,2,-7,8,2,3,1]

In this do for every index,

You will come to this:

nums = [-4,-3,-2,-7,8,2,-3,-1]

The element at index = 4 and index = 5 are positive.

So, the answer is [4+1,5+1] = [5,6].

Hope you understood this🔑.

Upvotes: 3

Related Questions