Finding number of elements within a given range in an array

Question

For example, lets say I have an array with the integers:

1 3 4 9 10

I want to find the number of elements between 1 and 9 (inclusive), so it should return 4 (as there are 4 integers [1,3,4,9] that are between one and nine inclusive).

One way I thought about doing this was to first place each integer J in the Jth position of the array so queries of whether the integer exists can be done in constant time. Then you can simply go through the range and check whether each number exists, but this takes too long for large numbers.

What is the fastest way to do it?

That runs in linear O(N) time. Amit's answer gives O(2lg(N)) which is even better! [lg(N) is log base 2] — 1110101001
– 1110101001, Commented Dec 14, 2013 at 20:26

Community · Accepted Answer · 2020-06-20 09:12:55Z

8

Just place the elements in a sorted array, then on query use binary search (twice) to find the lower and upper number, you get two indices l (lower),u (upper). The answer is then u-l + 1
Complexity is O(logN) - where N is number of elements in your array.

Indexing complexity (initializing the array, done only once) is O(nlogn) for sotring.

in your example:

binary search for 1 yields l=0
binary search for 9 yield u=3
answer = u-l+1 = 3-0+1 = 4

Note: If the array contains dupes or the numbers might not exist - some extra work is needed - but the idea how to do it remains the same.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Dec 14, 2013 at 20:23

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

1110101001 Over a year ago

This seems to be the best. Faster than going through the array every time. Thanks!

Ankit Garg · Accepted Answer · 2017-07-25 17:23:27Z

0

Amit answer is good if left and right interval are part of the array, what if array is

1 2 3 5 7 9 10

and interval is [2 8] In this case you cant search for 8 using binary search and wont get the count

The only solution i can think of is

for(int i=0;i<size_array;i++){
if(arr[i] >=left || arr[i] <= right)
count++;
}

can anyone come with a better solution ?

answered Jul 25, 2017 at 17:23

Ankit Garg

5662 silver badges12 bronze badges

Collectives™ on Stack Overflow

Finding number of elements within a given range in an array

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related