Find missing number

Question

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.?

Answer 1

Bishnu Chalise ,

> you should do a try by yourself first. save the code in playground and link it here.

Answer 2

Emerson Prado
https://code.sololearn.com/chqbqO8nOwC3/?ref=app

Answer 3

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/

Answer 4

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]

Answer 5

https://www.enjoyalgorithms.com/blog/first-missing-positive

Answer 6

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)

Answer 7

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.

Answer 8

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).

Answer 9

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))

Answer 10

Bishnu Chalise Could you save your code in Code Playground and add the link here? I'd like to test.

Answer 11

Bishnu Chalise Orin Cook I see. Time/space complexity is not my strength.

Answer 12

I have provided steps I have done in algorithm part only problem was what to do with duplicate numbers, how to handle them

Answer 13

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..

Answer 14

Thanks for your time. If I got solution I will definitely share it.

Answer 15

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 🥲

Answer 16

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..

Answer 17

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.

Answer 18

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.

Answer 19

Emerson Prado can it be done in constant space.? For storing Boolean I guess it may require another container...

Answer 20

"Same size as the input numbers list" is O(n) by definition, so that's linear space complexity unfortunately.