Thought process for the following problem?
Using O(n) extra space, you need to record start for each run of same numbers. Scan the array linearly. Once you removed a run, you either continue previous run, or start a new one.

for i:
  if a[i] != a[i-1]:
    if run[x] - run[x-1] &gt;= 3:
      x--
      // avoid copying the run into output array
    if a[run[x]] != a[i]:
      x++
    run[x] = i


On the second thought, you don't need the run[] array - only start the of current run. Once a run eliminated, you can check that previous run is at least 3 elements long in O(1) operations. You still need O(n) place to store the list of eliminated ranges, though.