+ 5

Find missing number

Must have: Linear time complexity Space complexity 0(1) Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well. For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3. Can you provide me algorithm to solve this.?

26th May 2023, 4:18 PM
Bishnu Chalise
Bishnu Chalise - avatar
20 Antworten
+ 6
Bishnu Chalise , > you should do a try by yourself first. save the code in playground and link it here.
26th May 2023, 5:22 PM
Lothar
Lothar - avatar
+ 5
The challenge and the constraints are indeed very tricky. I thought a lot about it. Python has an amazing data structure called heapq, and a normal list can be converted to it with the heapify method. Then it works like a priority queue, we can pop elements in increasing order. Heapify time complexity O(n) space complexity O(1) Heappop time complexity O(n log n) https://code.sololearn.com/c7zhMkg9XTDF/?ref=app https://stackoverflow.com/questions/38806202/whats-the-time-complexity-of-functions-in-heapq-library https://www.reddit.com/r/learnprogramming/comments/xvy6az/what_is_the_space_complexity_of_heapqheapifyx_in/
27th May 2023, 7:09 AM
Tibor Santa
Tibor Santa - avatar
+ 2
Those restrictions are tricky, linear time OR constant space would be one thing but I'm honestly not even sure how to get started here. I will say your proposed solution was clever, but always going to fail even without duplicates (assuming you meant the sum of all positive integers between the lowest and highest entries, otherwise it fails trivially by just always returning 0). Since they don't guarantee that the sequence starts at 1, or that there's only one missing number, the difference could end up being anything. eg for [1, 3, 5] your solution would return 6. Plus, your solution can't work if the next number isn't inside the range of numbers in the array, so it fails on the given example of [1, 2, 0]
26th May 2023, 6:06 PM
Orin Cook
Orin Cook - avatar
+ 2
Bishnu Chalise That hash in place algorithm is definitely better since it's non-destructive, yeah. I did make my solution work though, fwiw (just had to remember to take abs of the index during loop 3 in case a value got flipped before it was iterated through): https://code.sololearn.com/cvbotw7Kswwd/?ref=app (updated to also account for the case where the next "missing" number is just the next number)
27th May 2023, 4:38 AM
Orin Cook
Orin Cook - avatar
+ 1
If only one number was missing within the range *and* there were no duplicates, your suggested solution would work: iterate through to find N the highest number in the sequence and n the lowest, take (N+1)*(N/2) (the sum of integers from 1 to N), subtract (n-1), then iterate through a second time and subtract each member. Time is 2n which is linear, and space is just 3 ints (n, N, sum), so constant. But since none of those constraints are observed, idk that gets hard.
26th May 2023, 6:35 PM
Orin Cook
Orin Cook - avatar
+ 1
Alright, after a break and some more googling for ideas, I think this should work; it's not totally clear from the description whether we should be looking for any number > 0 or just within the existing range of numbers, so I made minor variants for both cases: iterate 1 (partial): find any positive number n; iterate 2: set all negative numbers and zeroes = n; iterate 3: for each entry arr[i] = x, if x < length of arr and arr[x] > 0 set arr[x] *= -1; iterate 4: find first positive entry arr[s] (s!=0) -> smallest missing positive number (starting from 0) = s iterate 1: find smallest positive number n; iterate 2: set all negative numbers and zeroes = n; iterate 3: for each entry x, if (x-n) < length of arr and arr[x-n] > 0 set arr[x-n] *= -1; iterate 4: find first positive entry arr[s] (s!=0); -> smallest missing positive number (starting from n) = s + n It's ugly and destructive so I can't call this a good solution, but it does satisfy the stated limitations (I think, unless I screwed something up lol).
26th May 2023, 11:03 PM
Orin Cook
Orin Cook - avatar
+ 1
I found this solution def _find_missing(nums): i = 0 while i < len(nums): while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i]-1] != nums[i]: temp = nums[nums[i]-1] nums[nums[i]-1] = nums[i] nums[i] = temp i += 1 for i, num in enumerate(nums): if nums[i] != i+1: return i+1 return len(nums)+1 arr = [1, 10,11,13] print(_find_missing(arr))
27th May 2023, 3:01 AM
Bishnu Chalise
Bishnu Chalise - avatar
+ 1
Bishnu Chalise Could you save your code in Code Playground and add the link here? I'd like to test.
27th May 2023, 3:28 AM
Emerson Prado
Emerson Prado - avatar
+ 1
Bishnu Chalise Orin Cook I see. Time/space complexity is not my strength.
27th May 2023, 4:20 AM
Emerson Prado
Emerson Prado - avatar
0
I have provided steps I have done in algorithm part only problem was what to do with duplicate numbers, how to handle them
26th May 2023, 5:24 PM
Bishnu Chalise
Bishnu Chalise - avatar
0
Orin Cook How would you approach if only one number was missing and all numbers were within range in unsorted order? I would be glad to hear your thoughts..
26th May 2023, 6:22 PM
Bishnu Chalise
Bishnu Chalise - avatar
0
Thanks for your time. If I got solution I will definitely share it.
26th May 2023, 6:37 PM
Bishnu Chalise
Bishnu Chalise - avatar
0
Well I've googled similar problems and I think even the XOR approach breaks down with duplicates, so I'm completely out of ideas. Good luck 🥲
26th May 2023, 6:49 PM
Orin Cook
Orin Cook - avatar
0
In line 3: It says find other words find lowest positive integer that doesn't exist in array which means the range doesn't matter which means we only need smallest positive integer..
27th May 2023, 2:51 AM
Bishnu Chalise
Bishnu Chalise - avatar
0
I tried your solution... But it failed for certain case, in iteration 3 if none of the if condition evaluates to true then test failed.
27th May 2023, 2:55 AM
Bishnu Chalise
Bishnu Chalise - avatar
0
Bishnu Chalise I could solve it via an auxiliary list of booleans of the same size as the input number list, representing the existing numbers. Each inputted number sets to True the corresponding item from the auxiliary list. At the end, the first missing number is the index of the first False item in this list. Or the next, if there's no False items.
27th May 2023, 3:38 AM
Emerson Prado
Emerson Prado - avatar
0
Emerson Prado can it be done in constant space.? For storing Boolean I guess it may require another container...
27th May 2023, 3:42 AM
Bishnu Chalise
Bishnu Chalise - avatar
0
"Same size as the input numbers list" is O(n) by definition, so that's linear space complexity unfortunately.
27th May 2023, 4:14 AM
Orin Cook
Orin Cook - avatar