CODEWITHSUNDEEP
data-structures
fmunshi
fmunshi

Reputation: 415

Create a data structure in O(n+k) time that can allow me to find the number of integers in some range in the array in constant time

I have an array of integers and I know the range of values of these integers

I want to create a data structure in O(n+k) time that can allow me to find the number of integers in some range in the array in constant time.

Is this possible, I don't want to sort the array though, is this possible with some sort of balanced tree? AVL trees?

Upvotes: 0

Views: 116

Answers (2)

DennyRolling
DennyRolling

Reputation: 486

tree operations are typically log(n)

I would have an array with the size of range which I would pre-fill with 'number of integers less than this value' and return difference between the min and max of range asked. that's const time.

Upvotes: 0

Zack Bloom
Zack Bloom

Reputation: 8417

You could create another array where the values are the number of values in the target array larger than the index. Then to find the number within the range, you simply need to find a[max] - a[min].

To create the array, you could iterate through the target array, incrementing the value at the index of the searching array (this is O(n)). Then you iterate through the searching array in reverse, making each value the sum of itself and all the values after it in the array (O(k), if k is the range of the data). Of course this would require quite a bit of memory, depending on the size of your array, but it would have the performance characteristics you require.

Upvotes: 1

Related Questions