2
\$\begingroup\$

The mission:

Zero Trim

Write a function which trims multiple zero's sequences to a single zero digit. The return value is the updated array. You are not allowed to use another array, and you need to implement it with one pass over the array. In other words, each element in the array should change its index only once during the program.

var w = [1,2,0,0,0,0,5,7,-6,0,0,0,8,0,0];

var n = zeroTrim(w);

console.log(n); //print [1,2,0,5,7,-6,0,8,0]

Best implementation should be in complexity of O(n), i.e., with one pass over the array.

I am allowed to use only: function,conditions (if), loops, --, ++, %, /, *, -, +, ==, !=, >=, >, <=, <, ||, &&, %=, /=, *=, +=, array.length, array.pop() and concat.

My code:

function zeroTrim(a){
  var i,j,l,last,count,count1;
  count=0;
  count1=0;
  
  for( i = 0 ;i < a.length ;i++){
  if(a[i] + a[i+1] === 0){
    count++;
    j=i;
    while(a[j] === 0){
      last=j;
      j++;
      count1++;
    }
    for(l=i ; l < a.length ;l++){
      a[l] = a[last];
      last++;
    }
  }
  }
  for(i = 0 ;i < count1-count ;i++ ){
    a.pop();
  }
  return a;
}


var a=[1,2,0,0,0,0,5,7,-6,0,0,0,8,0,0];
console.log(zeroTrim(a));

Any feedback would be appreciated, if you have other options please share it.

Thank you guys!

\$\endgroup\$
1
  • \$\begingroup\$ You didn't listed === in your allowed list but you are using it? \$\endgroup\$
    – tsh
    Nov 8, 2021 at 9:13

3 Answers 3

5
\$\begingroup\$

To make sure I understood the problem, I scribbled a simple solution.

// Trim multiple zero's sequences to a single zero digit. 
// The return value is the updated array. 
function zeroTrim(a){
    let j = 0;
    for (let i = 0; i < a.length; i++) {
        if (a[i] !== 0 || (i == 0 || a[i-1] !== 0)) {
            a[j++] = a[i];
        }
    }
    a.length = j;
    return a;
}

var w = [1,2,0,0,0,0,5,7,-6,0,0,0,8,0,0];
var n = zeroTrim(w);
console.log(n); //print [1,2,0,5,7,-6,0,8,0]

I then read your code. You have a lot of complicated, difficult-to-read code with a lot of loops.

Since one of your conditions is (a[i] + a[i+1] === 0), I ran a simple test.

var a=[42,-42];
console.log(zeroTrim(a)); //print [undefined, undefined]

That doesn't look right.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ This is a very clever and compact solution, but the access to a[-1] on the first iteration is a bit ugly. (I'd also point out that the correctness of the in-place modification is non-trivial, in the sense that even small and seemingly innocuous changes to the task and/or to the algorithm could easily break it. But since the OP's exercise requires it, I can't really criticize it as a design choice. If I saw this in code review at work, I would request a rationale for those choices and an outline of a correctness proof, though. And thorough unit tests, of course.) \$\endgroup\$ Nov 7, 2021 at 21:14
  • \$\begingroup\$ @IlmariKaronen: I added an explicit check instead of a[-1] as undefined. It goes without saying that there would be tests and proof of correctness. \$\endgroup\$
    – peterSO
    Nov 12, 2021 at 22:34
7
\$\begingroup\$

Like peterSO said in his answer your code appears complicated and it is not so easy to understand without an explanation of the task, moreover the (a[i] + a[i+1] === 0) condition brings with itself not conform outputs to what you expect. An approach to simplify your code is to use the fact that 0 is a falsy value and combine this with a variable storing the number of the ints you are saving in the array :

function zeroTrim(arr){
    let count = 0;
    let foundZero = false;

    for (const elem of arr) {
        if (elem || !foundZero) {
            arr[count++] = elem;
            foundZero = !elem;
        } 
    }

    arr.length = count;
    return arr;
}

console.log(zeroTrim([]));
console.log(zeroTrim([0]));
console.log(zeroTrim([0, 0]));
console.log(zeroTrim([1,2,0,0,0,0,5,7,-6,0,0,0,8,0,0]));

I used let, const instead of var like in your code because for me they help to read the code.

\$\endgroup\$
2
\$\begingroup\$

Your code is really hard to understand. You'll notice that the other answers found it so hard to understand that they basically ignored what you wrote and instead gave their own attempt. I think I've managed to get through what you intended.

  • You should prefer const if possible (not the case here), let if not const, and var if you have no other option.
  • As has been pointed out, it appears you're thinking that a[i] + a[i+1] === 0 is a shortcut for (a[i]===0)&&(a[i+1]===0). It's not, so I'll assume you have that instead.
  • Your variable names aren't great, and are the main source of confusion about what your code is doing. i, j, and l would possibly work for an index, but since you use all three in the same array, it's not clear what you mean by them. count would make sense if it's counting something, but since you also have count1, it's not at all clear what you're counting. I don't know what you mean by last, and the only reason that I know a is because of the problem description. My best guess at better variable names:
    • count1 -> zerosInBlocks
    • j -> zerosEndAt
    • count -> zeroBlocks
    • a -> array
  • Move the declarations to the tightest scope you can: j, l, and last are all within the if block. I'm also going to move let l and let i into the initializations of the for loops, although I've seen others complain about that.
  • last=j occurs in the while block, but doesn't do anything. Just move it after the block and say last=j-1.
  • last++ is at the end of the for loop, but l++ is the increment. They're doing the same thing, so lets put them in the increment area.
  • Now that we've gotten this far, I finally understand that the point of the l/last for loop is to move the rest of the array downward and overwrite the zeros. This needs a comment. This also means that you're making multiple passes over the array, and your algorithm is O(n^2). The better approaches in the other answers have two indices running through the array: i/elem is where the variables start and j/count is where they end up.
    • last -> moveFrom
  • Instead of popping individual items off the end of the array, we'll just redefine the length to be what we want.
  • I'm not seeing why j (now zerosEndAt) doesn't go past the end of the array in the while loop. I added that check. Your code has now become:
function zeroTrim(array){
    let zeroBlocks = 0,
        zerosInBlocks = 0;
    for ( let i = 0 ; i < array.length ; i++ ) {
        if ( array[i]===0 && array[i+1] === 0 ) {
            zeroBlocks++;
            let zerosEndAt = i;
            while ( zerosEndAt < array.length && array[zerosEndAt] === 0 ) {
                zerosEndAt++;
                zerosInBlocks++;
            }
            // move the rest of the array downward
            let moveFrom = zerosEndAt-1;
            for ( let l=i ; l < array.length ; l++, moveFrom++ ) {
                array[l] = array[moveFrom];
            }
        }
    }
    array.length -= zerosInBlocks-zeroBlocks;
    return array;
}

var array = [1,2,0,0,0,0,5,7,-6,0,0,0,8,0,0];
console.log(zeroTrim(array));
  • "Remove a bunch of stuff from the array" is basically the description of one use of the Array.splice function, although it appears you're not allowed to use that. But I'll continue. "Move the rest downward" becomes a.splice(i,zerosEndAt-i-1); (This is still probably O(n^2).)
  • Since the point of zerosEndAt is to count how many we're going to need to delete, let's do that. Instead of zerosEndAt, we'll use zerosInThisBlock. This also lets us move the zerosInBlocks increment out of the loop, and just update it after the loop. Your code has now become:
function zeroTrim(array){
    let zeroBlocks = 0,
        zerosInBlocks = 0;
    for ( let i = 0 ; i < array.length ; i++ ) {
        if ( array[i]===0 && array[i+1] === 0 ) {
            zeroBlocks++;
            let zerosInThisBlock = 0;
            while ( i+zerosInThisBlock < array.length && array[i+zerosInThisBlock] === 0 ) {
                zerosInThisBlock++;
            }
            zerosInBlocks += zerosInThisBlock;
            array.splice(i,zerosInThisBlock-1);
        }
    }
    array.length -= zerosInBlocks-zeroBlocks;
    return array;
}

var array = [1,2,0,0,0,0,5,7,-6,0,0,0,8,0,0];
console.log(zeroTrim(array));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.