thedeployguy

switch-check
switch-x

Leetcode 448 Find All Numbers Disappeared in an Array

January 21, 2021

Welcome back, part of my Self Development Goals for 2021 is “Complete at least 25 - 50 Leetcode Questions”, today we are going to discuss and solve Leetcode Leetcode 448 Find All Numbers Disappeared in an Array

Find All Numbers Disappeared in an Array Problem

Find All Numbers Disappeared in an ArrayProblem

Find All Numbers Disappeared in an Array Solution 1

As with every leetcode problem there are various ways to solve this, I have added 3 different solutions into the comments with different time and space complexities. The solution I will go into detail will run in O(n) time and O(1) space but any of the solutions would pass in leetcode.

# Pseudocode

        for all numbers in array
            Each number is treated as index (-1)
            Mark that "index" in the array as "seen" (add a -)
        Any positive indexes left will be numbers missing
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        # Alternative Solution 1:
        #   Generate hashmap of 1..n
        #   Mark each number in hashmap as "seen"
        #   Find values in hashmap that are 0 and return it
        # Time Complexity: O(n)
        # Space Complexity: O(n)

        # Alternative Solution 2:
        #   Sort list O(n log n)
        #   check index + 1 = cur if not then it missing
        # Time Complexity: O(n log n)
        # Space Complexity: O(n)

        for i, num in enumerate(nums):
            # real index num - 1
            rIndex = abs(num) - 1
            # Take the value at that index and make it negative
            nums[rIndex] = abs(nums[rIndex]) * -1

        return_list = []
        # Any numbers that are positive add index + 1 them return list
        for i,num in enumerate(nums):
            if num > 0:
                return_list.append(i + 1)

        return return_list

Time / Space Complexity

Time: O(n)

Why: We need to go through each number and mark it as “seen”, then go through each number again to find any positive numbers.

Space: O(1)

Why: We are modifying the existing array so we are not using any extra space.

Conclusion

I hope you enjoyed this second post on solving some Leetcode problems, Anyway, that is 5 / 25 for my yearly goal done! now onto the rest, i hope you enjoyed this post!

Until next time

Jason


Personal Blog by Jason Lloyd.
I talk about programming, life, self-development and everything in-between.