I have an array which is taking in values. at some point during this process, a “find(n, x)” command is given as input. The find command is supposed to find the number of occurrences of n between index x and current index. x is definitely less than the current index. For example, the input goes like:
1
2
3
2
1
4
1
find(1, 3)
2
2
4
1
find(2, 3)
%------------------%
output:
2 (because there are 2 ones between index 3 and the index when find(1, 3) is called).
3 (because there are 2 twos between index 3 and the index when find(2, 3) is called).
%------------------%
How can I implement this? please explain.
If each element in the array is small (ie, you can make an array of that size), store for all numbers the index of their occurrences.
Eg, the array for number 1 would be [0,4,6,10].
When a query comes, do a binary search on the list of that number to find the required count.
Complexity O(Qlog(N)), N being the size of array
If each element can be large, I can always map the entries of the array to a permutation of [1…N], where N is the size of the array.
Eg, if the array is [13,1,12,13], I will call the array [3,1,2,3] and do mapping 13->3, 1->1, 12->2.
After that, the solution to case 1 would work.
2 Likes
Can you do it using binary indexed trees?