Algorithm for grouping identical neighbors in a list

Question

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

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

Answer 1

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.)