DEV Community

Mridu Bhatnagar
Mridu Bhatnagar

Posted on

2

Day-12 Find all the numbers disappeared in the array

This problem statement is a part of LeetCode's learning card Introduction to Data Structures Fun with Arrays-101.

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.

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

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

Output:
[5,6]
Solution Approach
  1. The range of elements and the value of elements is the same.
  2. List can have duplicates as well. So, converting a list to set would mean removing duplicates and having only unique elements.
  3. Subtracting the set containing numbers between range [1, n] and the set formed by removing duplicates. Would return the missing elements.
  4. Convert the set to list.
class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        return list(set([x for x in range(1, len(nums)+1)]) - set(nums))
Learnings
  1. Time complexity - 0(n)
  2. We are still using extra space by initializing a completely new list with elements between [1,n].
  3. Need to figure out a way to optimize space.

Top comments (0)

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay