How to implement space trimming on a simple array

Question

This is more of a pseudo code question. Lets say we have an char array where each value is either a letter or a space. What we need to implement is an algorithm thats replaces any sequence of spaces with a single space.

Example:

the array:

['a', 'b', ' ', ' ', ' ', 'b', 'c', ' ']

should become:

['a', 'b', ' ', 'b', 'c', ' ']

This algorithm should only modify the given array and not use in temporary arrays or anything like that. The only way to change the array is by setting items by index (can't use any fancy array function like arr.remove(0, 2), only use arr[i] = b). Is there a solution in O(n)?

Any pseudo code or real programming language solution that answer the restrictions is good.

Answer 1

You could take beside the normal index i for iterating the array, another index, here l for keeping the last new index for the last valid character. If actually no space or no space at the last index is available, then a shifting of the value takes place and the last index is increased.

Inside of the array increase the index i.

Finally adjust the length of the array to l.

 i    l    0  1  2  3  4  5  6  7
--   --   -----------------------
           a  b  _  _  _  b  c  _
 0    0    a
 1    1    a  b
 2    2    a  b  _
 3    2    a  b  _
 4    2    a  b  _
 5    3    a  b  _  b
 6    4    a  b  _  b  c
 7    5    a  b  _  b  c  _

var array = ['a', 'b', ' ', ' ', ' ', 'b', 'c', ' '],
    i = 0,
    l = 0;
    
while (i < array.length) {
    if (array[i] !== ' ' || array[l - 1] !== ' ') {
        array[l] = array[i];
        l++;
    }
    i++;
}

array.length = l;

console.log(array);