CODEWITHSUNDEEP
algorithmdata-structures
aspen100
aspen100

Reputation: 965

Insertion into a sorted list, in constant time

I have a sorted list of integers, and I wish to insert into this list any element, in constant time. I'm allowed to do some pre-processing, as long as it will let me run this operation in constant time (i.e., no matter how many times I repeat this operation after the pre-processing, it should run in constant time).

How can this be done?

Edit : I can think of a couple of more constraints to make it a bit less ambiguous, and a bit more challenging to solve -

  1. list needs to be maintained in sorted order post-insertion(s)
  2. Or, list needs to somehow support max/min operations in constant time post insertion(s).

Upvotes: 5

Views: 4785

Answers (2)

Muli Yulzary
Muli Yulzary

Reputation: 2569

Use a LinkedHashMap. Decide how many elements are stored per hashcode (lets say integers 0-10 are hash(1), integers 11-20 are hash(2) and so on...)

When you read an integer, calculate its hash O(1) -> access the hashmap (roughly O(1)) -> insert to list as first element O(1). If you want to allow duplicates extend each element in the list into its own list or use a counter for each element.

Upvotes: 2

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18148

You can put the integers into a radix tree, treating the integers as bit strings. With a radix of 2 and a list of 32-bit integers you'll have a maximum tree depth of 32, which is your constant factor for constant-time insertion (you wouldn't ordinarily do something like this because the constant factor for the radix tree is probably going to be larger than the log factor of a balanced binary tree, plus all of the bit twiddling you'll need to do in for the radix tree is going to be costly)

Upvotes: 7

Related Questions