Linkedlist keep track of min in constant time?

Question

EDIT:

This isn't as trivial as you think. Consider the fact that each addition of a new number pushes out an old number from the linkedlist.

The solution doesn't seem to be as simple as keeping track of a min number with a variable. What if the minimum gets pushed out of the linkedlist? Then what? How do you know what the new min is?

I heard this interview question:

You have a fixed length linked list.

• At time t=0, the linkedlist is filled with random numbers.

• At each increment in time, one new number is fed into the head of the linkedlist, and one number is pushed out from the tail.

• You are allowed only ONE traversal before the first time interval.

  • This means one traversal ever. Not once at every time t.
    .

• O(1) storage.

Your task is to be able to return the min of the linkedlist at every time interation.

What is an algorithm that would be able to do this?

---

Interesting note:

Since there's no information regarding time complexity, you are allowed to use sort operations. The only problem then is: sorting takes more than one iteration.

Answer 1

First,

O(1) storage is not the same as an a single register. It means constant space usage.

Second,

I am going to call your LL a constant size queue (CSQ).

When initializing your queue, also initialize a min-heap where all elements of the queue keep a reference (pointer) to the heap node corresponding to them.

1 op on CSQ

• Pop 1 element out in O(1) time of the CSQ.
• Remove corresponding node from the min-heap in O(lg n) time.
• Add corresponding element to the min-heap in O(lg n) time.
• Push 1 element into the CSQ in O(1) time and mark a reference to the heap node added above.

The above operations guarentee that the heap size will always remain in sync with the queue size --hence O(1). The heap can be constructed in a single travesal.

Finding min

Clearly O(1). Just return the head of the min heap.