Remove adjacent duplicates on array

Question

Suppose we have an array of numbers like the next one:

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

The goal is to remove duplicates values, but only if they are adjacent. So, the expected output for the previous sample should be:

[2, 0, 2, 3, 0, 1]

So far, I managed to almost solve this using a recursive approach, but for some reason that I can't figure, the generated result is not returned (however, you can see it on the log before the returning condition).

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

const remAdjDups = (arr, output = []) =>
{
    if (!arr.length)
    {
        console.log("Result before return: ", output);
        return output;
    }

    if (arr[0] === arr[1])
    {
        arr.splice(1, 1);
        remAdjDups(arr, output);
    }
    else
    {
        remAdjDups(arr.slice(1), output.concat(arr[0]));
    }
}

let out = remAdjDups(input.slice());
console.log("output: ", out);

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

So, first and mainly, I will like to understand what is happening with my approach, and second I'm open to any other approach (of any type) that could solve this problem.

Updated Solution

Just in case anyone is interested, I have finally solve this problem using recursion this way. I know filter solution is shorted and elegant, but I was training solving by recursion.

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1, 1, 1, 1];

const remAdjDups = ([x, y, ...rest], out = []) =>
{
    if (!rest.length)
        return (x === y) ? [...out, x] : [...out, x, y];
    else if (x === y)
        return remAdjDups([x, ...rest], out);
    else
        return remAdjDups([y, ...rest], [...out, x]);
}

let out = remAdjDups(input.slice());
console.log("output: ", out);

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Nurbol Alpysbayev · Accepted Answer · 2019-02-09 05:18:22Z

12

Regarding your solution, just add return before remAdjDups(arr...

P.S.

I used Array.prototype.filter for that

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

const result = input.filter((i,idx) => input[idx-1] !== i)

console.log(result)

edited Feb 9, 2019 at 5:18

answered Feb 9, 2019 at 5:13

Nurbol Alpysbayev

22.4k6 gold badges68 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Shidersz Over a year ago

Ok, this is nice approach! However, I'm mainly interested on why my approach isn't working.

Nurbol Alpysbayev Over a year ago

@Shidersz I've already updated my answer to answer that as well (before you wrote your comment)

Shidersz Over a year ago

I can't believe I missed that, I should delete the question, if wasn't because I already voted on your answers...

Nurbol Alpysbayev Over a year ago

@Shidersz Happens to all of us! Why delete? No one has flagged it as unappropriate or duplicate. Hence you should choose the best answer (probably considering also which one appeared earlier).

Code Maniac · Accepted Answer · 2019-02-09 05:15:39Z

2

You can use filter

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

const result = input.filter((i,index) => {
 if(index != 0){
  return input[index-1] !== i
 } 
 return i
})

console.log(result)

answered Feb 9, 2019 at 5:15

Code Maniac

37.9k5 gold badges44 silver badges65 bronze badges

Comments

Mulan · Accepted Answer · 2020-08-07 03:08:53Z

Recursion by mathematical induction works nicely for this problem -

If the first element, a, is null, return the empty result
(induction) the first element is NOT null. If the second element, b, is null, return a singleton array of the first element, a
(induction) neither the first element NOR the second element are null. If a is equal to b, return the recursive result with a removed
(induction) neither the first element nor the second element are null and they are NOT equal to one another. Return the recursive result without removing either a or b

const removeDupes = ([ a, b, ...more ]) =>
  a == null
    ? []                                  // 1
: b == null
    ? [ a ]                               // 2
: a === b
    ? removeDupes([ b, ...more ])         // 3
: [ a, ...removeDupes([ b, ...more ]) ]   // 4

const input =
  [2, 2, 0, 2, 3, 3, 3, 0, 0, 1, 1];

const result =
  removeDupes(input)
  
console.log(result)
// [ 2, 0, 2, 3, 0, 1 ]

Prasun · Accepted Answer · 2019-02-09 05:17:34Z

1

Your approach is correct, you just forgot to return the result from the recursive call. All you need is to add return statement.

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1];

const remAdjDups = (arr, output = []) =>
{
    if (!arr.length)
    {
        console.log("Result before return: ", output);
        return output;
    }

    if (arr[0] === arr[1])
    {
        arr.splice(1, 1);
        return remAdjDups(arr, output);
    }
    else
    {
        return remAdjDups(arr.slice(1), output.concat(arr[0]));
    }
}

let out = remAdjDups(input.slice());
console.log("output: ", out);

Hope this will help!

answered Feb 9, 2019 at 5:17

Prasun

5,0132 gold badges23 silver badges23 bronze badges

Comments

Amardeep Bhowmick · Accepted Answer · 2019-02-09 05:19:41Z

1

Yo need to use return in the if and else blocks of your code as otherwise undefined is going to be returned.

if (arr[0] === arr[1])
{
    arr.splice(1, 1);
    return remAdjDups(arr, output);
}
else
{
    return remAdjDups(arr.slice(1), output.concat(arr[0]));
}

This is another approach using Array#reduce

const input = [2, 2, 0, 2, 3, 3, 0, 0, 1, 1, 1, 1, 6, 3, 3, 5, 8, 8, 0, -1, -1, 2, 56, 57, 56];

const arr = input.reduce((acc, ele, idx) => {
  if(ele !== input[idx + 1]){
   acc.push(ele)
  }
  return acc;
}, []);

console.log(arr);

answered Feb 9, 2019 at 5:19

Amardeep Bhowmick

17k3 gold badges33 silver badges46 bronze badges

Collectives™ on Stack Overflow

Remove adjacent duplicates on array

Updated Solution

5 Answers 5

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Updated Solution

5 Answers 5

4 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related