CODEWITHSUNDEEP
algorithmsorting
pizzarob
pizzarob

Reputation: 12039

Algorithm to find correct index

I have an array and a map. The array contains a list of numbers the map contains a key (integer) value (boolean) pair telling us which items have been removed from the list.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

And a map telling us which items have been removed:

{ 3: true, 4: true, 5: true, 6: true, 7: true, 8: true, 9: true }

The items remain in the array, but are not counted toward the index when looking up an item in the array by index.

For example, given the above, index 2 would return 10:

[1, 2, x, x, x, x, x, x, x, 10]

-0--1------------------------2-

We can loop through each item in the list to see if it is in the map, but worst case the complexity would be O(n) and if there was one billion items in the list this would be a problem. Is there a better way to determine the correct index? I have thought of using a batch type binary tree - each node would hold a sequential range (if a sequential range exists), or a single number, but even then - if every other item was removed - worst case would be O(n) since there would be no sequential ranges.

Upvotes: 0

Views: 243

Answers (1)

Shuki Avraham
Shuki Avraham

Reputation: 1043

You can use a binary tree with an extra property that each node will hold the number of removed items in its subtree. update that value when you insert or remove an item. To find the index of an item, find it on the tree and for every right turn in the search add the number of removed items of the left subtree.

Upvotes: 2

Related Questions