JavaScript : How can I sort values in a dictionary to output matched values and ouput the values that don't match showing an empty result

Question

I have a set of data as follows
Left: Right:

1 1
2 2
3 3
5 4
7 6
9 8
1 10

I want the output / result to be this
Result

1 / 1
2 / 2
3 / 3
- / 4
5 / -
- / 6
7 / -
- / 8
9 / -
10 / 10

I have structured my two sets of data into a dictionary

key: 1, value {left: 1 right: 2} etc

How do i sort these and match them based on value? any help is appreciated.

please add a data structure to the question and how the items are splitted to a new data set. what happens to 1/10? — Nina Scholz, Jan 21 '19 at 10:13
Should the last 2 lines of the result be 9 / - and - / 10 , there would be some logic in that? — Matthew Page, Jan 21 '19 at 10:16
https://stackoverflow.com/questions/12433604/how-can-i-find-matching-values-in-two-arrays — bmz1, Jan 21 '19 at 10:24

score 1 · Answer 1 · answered Jan 21 '19 at 10:26

// Assuming you have two sorted arrays
left = [1,2,3,5,7,9,10]
right = [1,2,3,4,6,8,10]

let i=0;j=0;
// Assuming you only have to print the result
while(i<left.length && j<right.length) {
  if(left[i] == right[j])
    console.log(left[i++] + ' / ' + right [j++]);
  else if(left[i] < right [j])
    console.log(left[i++] + ' / -');
  else
    console.log('- / ' + right[j++]);
}
while(i<left.length) {
    console.log(left[i++] + ' / -');
}
while(j<right.length) {
    console.log('- / ' + right[j++]);
}

Do note there if the arrays are not sorted, there are more optimal ways to achieve this than sorting the two arrays.

score 0 · Answer 2 · answered Jan 21 '19 at 10:33

0

Try something like this:

        Array.prototype.max = function(){
          return Math.max.apply(null, this);
        };

        Array.prototype.min = function(){
          return Math.min.apply(null, this);
        };

        function onlyUnique(value, index, self){ 
            return self.indexOf(value) === index;
        }

        var a1 = [1,2,3,5,7,9,1],
            a2 = [1,2,3,4,6,8,10];
            min = [
                a1.min(), a2.min()
            ].min(),
            max = [
                a1.max(), a2.max()
            ].max(),
            res = [],
            arr = a1.concat(a2).filter(onlyUnique).sort((i1,i2) => i1-i2)

        for(var i=0; i<arr.length; i++){
            var n = arr[i]

            res.push({key: n, value: {
                left:  a1.includes(n) ? n : '-',
                right: a2.includes(n) ? n : '-'
            }})
        }

        console.log(res);

answered Jan 21 '19 at 10:33

Vitalii

161
1
10

the time complexity of the solution is very high! If you have two arrays of length m and n, you are making a new array m+n and sorting it! That would have O((m+n)log(m+n)) whereas you can achieve the solution in linear time O(n) – Dhananjai Pai Jan 21 '19 at 10:39
@DhananjaiPai there is a good example to help JS beginners**understand** how its work and how to solve problem step by step. – Vitalii Jan 21 '19 at 10:44
I am sorry, but I beg to differ. This is an overly complicated example that uses functions unnecessarily to do a simple comparsion – Dhananjai Pai Jan 21 '19 at 10:47
@DhananjaiPai this is a good practise. Your example is work fine but isn't readable and will generate a troubles if you will try add more arrays. Additional while and if/else for each array? This isn't good solution. – Vitalii Jan 21 '19 at 10:51
It is a bad practise to update the prototype without necessary. It creates confusion within the team whether you are using javascript code or custom function. My code is however based on the assumption that the arrays are sorted. I can still give an O(n) solution even if it is not sorted. You have clearly not read the clarification to the question that the last number is indeed `10` and not `1` – Dhananjai Pai Jan 21 '19 at 10:55
And clearly I misread your code and the complexity is worse than O((m+n)log(m+n). It would be O((m+n)^2) since you are using an indexOf inside a filter. To compare, if the original size was 100 each. your solution would take 200*200 = 40000 comparisons to generate output. I can get the solution with probably a little over 100 comparisons. – Dhananjai Pai Jan 21 '19 at 10:58
lmao it is a good practise to use prototype in prototype-based language. Your code is just another example of hard code that potentially generate troubles in future. – Vitalii Jan 21 '19 at 10:58
roftlmao, I clearly can't know where you get this from, but you should not override the standard objects. It is prototype-based and you can use your own custom functions and objects to utilize the powers. I was trying to solve the problem at hand. I can write an optimal solution either way, but this is not about showing off. – Dhananjai Pai Jan 21 '19 at 11:01
@DhananjaiPai do you read what I write at first comment? IT IS HELPFULL EXAMPLE TO UNDERSTAND LOGIC FOR BEGINNERS, not IT IS EXAMPLE HOW TO OPTIMISE CODE. – Vitalii Jan 21 '19 at 11:03

score 0 · Answer 3 · answered Jan 21 '19 at 10:40

Something like this could work, event though not perfect:

const data = [{key: 1, value {left: 1 right: 2}}, ...]

const leftValues = data.map(d => d.value.left).sort()
const rightValues = data.map(d => d.value.right).sort()

// assuming same length for left and right arrays
for (let i = 0; i < leftValues.length; i++) {
  const left = leftValues[i]
  const right = rightValues[i]
  if (left === right) {
    console.log(`${left} / ${right}`)
  } else if (left < right) {
    console.log(`${left} / -`)
  } else if (right > left) {
    console.log(`- / ${right}`)
  } else {
    // do your thing
  }

}

JavaScript : How can I sort values in a dictionary to output matched values and ouput the values that don't match showing an empty result

3 Answers3