World's most popular travel blog for travel bloggers.

Algorithm for grouping identical neighbors in a list

, , No Comments
Problem Detail: 

I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries.

Example list:


After 'compression'


Is there an algorithm for doing this that is faster than O(n)? In other words, faster than just looking at the next neighbor?

while (1)     n = 0, m = 1     if (list[n] == list[m])         remove list[m]     else          n = m         m = m + 1     if (m > list.size)         break 

If not, what about this problem makes it O(n)?

Asked By : OrangeSherbet
Answered By : Yuval Filmus

You can use an adversary argument (exercise) to show that any algorithm which outputs the correct "compression" must examine all entries in the input, in every case. Such an algorithm cannot run in $o(n)$ on any input.

To answer your question, the reason that this problem requires a running time of $\Omega(n)$ is that the output depends on all entries of the input, in the sense that for every input and every entry there is a way to change the entry that affects the output. (Note, however, that not every change to the input results in a change to the output: for example $1,1,2$ and $1,2,2$ have the same output, but $1,3,2$ does not.)

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback