Cheap and Secure Web Hosting Provider : See Now

# Algorithm for grouping identical neighbors in a list

, ,
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:

1,1,1,1,1,2,2,2,3,3,1,1,1,2,2,2,2,2,2,2,2,2,4,4,4,4,1,1,1,1,1,1 

After 'compression'

1,2,3,1,2,4,1 

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 

###### 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 : http://cs.stackexchange.com/questions/56491

3200 people like this