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
EDIT: misunderstood problem, ignore
"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
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 ?
example if array is [1,3,4,5] then the smallest positive integer which is missing is 2
Ohhh sorry I understood it wrong I thought you want the first integer that was outta place not the smallest
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.
Thanks a lot for this. Helped a lot !!
You are welcome :)
try Mo's algorithm, i know that this algo can help a lot to solve this problem and it's easy to code
I think Mo's algo will give TLE as N<=10^6. However I got the solution. Refer to this comment
I know that you found the answer, but you can see this. (O(QlogN) with segment tree)
@tanmay did you got the interview call
Yes
[DELETED]
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.
I guess you can find the first missing positive integer in a range in O(log(N)) time by using binary search. You would have something like log(Q * log(N)).
it's not binary searchable :|
we can use a segment tree to find it.
haha but the blog was 7 years ago anyway.