Sorted Union bug

JavaScript
1

I wrote a code to solve “Sorted Union problem”. However, the problem is not getting solved, when i enter a particular test case it shows solved for only that particular case. How is this possible? If all cases are solved individually, Shouldn’t it be solved ?

i dont know if this is a bug or any error on my part.

Here is my code

 var arr2 = [] ;

function check(x)
{  for ( var i = 0 ; i < arr2.length ; ++i )
    if ( x == arr2[i] ) 
      return 0 ;
   if ( i == arr2.length) 
     return -1 ;
}

function uniteUnique(arr) 
{ for (var i = 0 ; i < arguments.length ; ++i )
    for ( var j = 0 ; j < arguments[i].length ; ++j )
    { //console.log(check( arguments[i][j] )) ;
      if ( check(arguments[i][j]) == -1)
        arr2.push(arguments[i][j]) ;
    }
  return arr2;
}

console.log(uniteUnique([1, 2, 3], [5, 2, 1, 4], [2, 1], [6, 7, 8])) ;
2

I think I had a similar problem when I declared an array globally at the top. I had to move it inside my unite function. Obviously you’d have to pass it into check() if you try that though.

3

@manan999, you’ve just run into the horror that is “global mutable state”.

Because push changes (or mutates) the underlying array, every invocation of uniteUnique has the side-effect of leaving arr2 permanently altered. When the function is called again, it does not start with a blank array as you seem to expect, but with an array filled with the previous answer.

One solution is as @shootersf suggests: get rid of the global variable.
Another solution is to avoid side-effectful functions like push.

2 Likes
4

Thanks for the solution @shootersf @frenata

Are there any better alternatives to push() then?

1 Like
5

You might find concat useful.

6

Ah that makes sense. I never thought about the algorithms in terms of all the checks using the same script rather than a new copy of it everytime so the global variable would persist from check to check. So, a bad and hacky type of fix would be to declare the variable globally and assign it an empty array at the start of the unite function. Right?

I see why that is terrible design though. It just helps to understand what is going on better.

7

Sure, that should absolutely work.

1 Like
8

The problem is still there on using concat(), the trick suggested by @shootersf is the only thing that seems to work

9

Eliminating global state is great! It should be avoided as much as possible.

To (maybe) spark someone’s imagination, here’s a method using concat, reduce, and filter to do this without any array mutation at all:

function uniteUnique(arr) {
 
  // grab the arguments into an array
  let args = Array.from(arguments);
  
  // reduce the args into a single array
  let unique = args.reduce(
    
    // the reduction function: it operates on each element
    // and collects them into an accumulator value
    function(accumulator, array) {
      
      // first figure out which values are *new* with filter
      let newvalues = array.filter(
        function(value) {
          
          // only keep the values that aren't already in the accumulator
          return !accumulator.includes(value);
        });
      
      // after figuring out which values are new, add them to the accumulator
      // and return. the returned value will be the new accumulator for the
      // next iteration of the reduction function
      return accumulator.concat(newvalues);
      
  }, []); // the initial value for the accumulator, the empty array
  
  return unique;
}

Or more succintly:

function uniteUnique(arr) {
 return Array.from(arguments)
    .reduce((acc, a) => 
            acc.concat(a.filter(x => 
                                !acc.includes(x))));
}