### tanmaydatta's blog

By tanmaydatta, history, 6 years ago,

I recently gave a hiring test and was stuck on a particular problem. The problem is as follows:

You are given an array A of N elements and Q queries of the form L,R.

For every query find the first missing positive integer in the range A[L],A[L+1],A[L+2] ...... A[R].

N <= 10^6

Q <= 10^6

1<= A[i] <= 10^9

I know how to find the first missing positive in O(N) but don't know how to handle multiple queries in less time. Any help would be appreciated. Thanks

• +47

 » 6 years ago, # | ← Rev. 3 →   0 EDIT: misunderstood problem, ignore
•  » » 6 years ago, # ^ |   +3 "each node storing info about the leftmost non-positive integer in range" How would you combine the results? (combining results in query)Like left side has {3, 5} with first non-positive integer as 1. Right side has {1, 2} with first non-positive integer as 3
 » 6 years ago, # |   0 If I understood the problem correctly you can find the position of all the missing positive integers in o(n) and store them in a set then when you have a query just do a lower bound on that set.Again I might have understood the problem incorrectly can you define what is the first missing intger ?
•  » » 6 years ago, # ^ |   0 example if array is [1,3,4,5] then the smallest positive integer which is missing is 2
•  » » » 6 years ago, # ^ |   0 Ohhh sorry I understood it wrong I thought you want the first integer that was outta place not the smallest
 » 6 years ago, # |   +55 What I am going to explain is an offline O(Q * logN) solution.Let's observe that the answer for a query will never be more than N + 1. This means that we can simply ignore numbers greater than N + 1 in the steps I am going to explain.Now, let's loop from left to right (say we use i for the loop) and at any point of time, we store the last occurrence of each value last[value] (considering only values  ≤ N + 1). Let's take a look at some query [L;R] for which R = i. The answer will obviously be the smallest integer for which last[value] < L.In order to find the smallest integer for which last[value] < L, we can build a segment tree, in which the indices correspond to value, the leaves store last[value] and the internal nodes store the minimum for their subtree. Here comes this fairly well-known binary search on segment tree. We start at the root. If the value stored in the left child of the current node is  < L, then we go to the left child. Otherwise, we visit the right child. We repeat this until we reach a leaf node and the index of this leaf node will be the answer for the query.A really similar problem can be found here with the only difference that it asks for the smallest non-negative integer missing. I solved it recently, my code is here.
•  » » 6 years ago, # ^ |   +3 Thanks a lot for this. Helped a lot !!
•  » » » 6 years ago, # ^ |   +3 You are welcome :)
 » 6 years ago, # |   0 try Mo's algorithm, i know that this algo can help a lot to solve this problem and it's easy to code
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 I think Mo's algo will give TLE as N<=10^6. However I got the solution. Refer to this comment
 » 6 years ago, # | ← Rev. 9 →   +12 I know that you found the answer, but you can see this. (O(QlogN) with segment tree)
 » 6 years ago, # |   +5 @tanmay did you got the interview call
•  » » 6 years ago, # ^ |   +8 Yes
 » 6 years ago, # | ← Rev. 2 →   -8 [DELETED]
 » 6 years ago, # | ← Rev. 3 →   +2 I think persistence segment tree will work in O(log N) per query.. after compressing the A[i] values. You must compress the A[i] values such that no 2-non consecutive values gets the consecutive values in the compressed array.EDIT: I don't think it will be able to handle the duplicates. So, this solution will not work. Although an offline solution with persistent tree should work similar to the one proposed by @X-tazy.