I’m new here and I’m doing one question. How can I determine whether any integer in arr2 is in the range of a limit?
I found a solution on leetcode by doing lower bound and upper bound, but I have a doubt that when we do lower bound, we get elements greater than or equal to and when we do upper bound, we get elements less than or equal to, and there they have written if (lower bound() == upper bound(),increment the count. I mean, if they’re comparing iterators, and the limit is -7,11, then lb can be -6 if discovered, and UB can be 10,how then comparing them gives a check is there any element exist between them? Their iterator position differs; how are we obtaining this, or is there another method?
You can generate a prefix array, if each element is at most 10^6.
For example,
if the array is 1 2 4 6 8,
the prefix array will look like this: 0 1 2 2 3 3 4 4 5, where each index stores the count of elements less than or equal to it.
Now for checking the numbers within a range [l,r] simply use prefix[r] - prefix[l-1]
If the numbers can reach upto 10^9, this method will fail.
Then, sort the array : 1 2 4 6 8
After that, if the range is [L,R], compute the lower_bound of L-1. You’ll get the index. If the index is i, it means i elements are before that number L. Similarly, compute lower_bound of R. Now subtract R’s index from L’s index, you’ll get your ans.
1 Like
IN one of the leetcode solution it was written that (lowerbound(a.begin(),a.end(),d1) == (a.begin(),a.end(),d2) where d1=7 and d2 =11 he was doing compassion this way. how this way can lead to check whether any element exist between d1 and d2