First Missing positive in a range

Revision en1, by tanmaydatta, 2017-05-14 19:39:50

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English tanmaydatta 2017-05-14 19:39:50 509 Initial revision (published)