forked from super30admin/Array-2
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMissing Elements in Array
More file actions
34 lines (32 loc) · 1.37 KB
/
Missing Elements in Array
File metadata and controls
34 lines (32 loc) · 1.37 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
Appproach 1 : Using HashMap. Store wat's there in given array. Key would be value of the array and value will also be the same.
Time complexity : O(N)
Space Complexity : O(N). Result array has been created to add the missing elements
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
hashmap={}
print(len(nums))
for num in nums:
hashmap[num]=num ### Store all the values of the array as the key value pairs
print(hashmap)
result=[] ### to store the missing values
for num in range(1,len(nums)+1):
if num not in hashmap:
result.append(num)
return result
Approach2 : Inplace solution. Make use of input array to mark the numbers visited and then find our missing numbers.
Treat the numbers in the array as indices and mark the corresponding locations as negative
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
result=[]
for i in range(len(nums)):
temp=nums[i]
## if found index element is negative
if temp<0:
temp*=-1 ### Absolute value
#temp=abs(temp)-1
if nums[temp-1]>0:
nums[temp-1]*=-1
for i in range(len(nums)):
if nums[i]>0:
result.append(i+1)
return result