Removing specific Arrays out of multidimensional arrays

Question

I have this array, but not in any guaranteed order:

[ [2,1], [2,2], [2,3], [3,1], [3,2], [4,1], [4,2], [4,3], [4,4], [5,1], [5,2] ]

I need to cycle through it, match the ones with the same arr[0] value, and then remove the one with the highest value at arr[1]. It should end up looking like this:

[ [2,1], [2,2], [3,1], [4,1], [4,2], [4,3], [5,1] ]

I'm not sure exactly how to iterate through this accurately. Most places I have seen ways to filter complex objects, or remove single values from one-dimensional arrays.

I have only really gotten into using arrays in the last few days. Thanks for the help!

• Daniel Gimenez: Can we assume it is sorted?
• McPhelpsius: Not necessarily. The objects get pushed into the array on random user clicks.
• rink.attendant.6: Will all of the pairs be unique (i.e. there won't be more than one [2,1]) ?
• Daniel Gimenez: What happens if there is only one instance, such as [6,1]?
• McPhelpsius: Yes. On click of [2,1], [2,2] would be created. If [2,2] is clicked, [2,3] is created

Answer 1

Okay I have two solutions. version1 is basic and could use some optimizing while version2 should be faster with bigger, evenly distributed lists.

If you're only going to have a few items, use one. It only has a few lines of code, so it won't be a distraction. If you have a big array and it'll be pretty evenly distributed, then use two.

I actually did a test with the sample data, and version2 has less iterations than version1. V1 ran 11 times in the outer loop, and 79 times in the inner loop. V2 ran 11 times in the first outer loop, 4 times in the second one. The inner loop of the second loop ran 11 times, and the loop inside that ran only 7 times. So the total iterations of v2 was about 40% of v1. When I double the items, v2 only uses 30% of the iterations.

Version2 has a couple of other potential advantages.

• I believe Array.push has a higher performance cost than Array[index] =. If that's true, then you know that newAry will have a final length of the origianl array's length - the length of the indicies array length. So you can initialize newAry with that length, keep a counter variable, and then do something like newAry[counter++] = someVal.
• There was some discussion if you wanted to keep a result if there was only one. If that is the case, it is easy to do a check at the start of the second loop: if (iVal.length == 1) // add to newAry else do j,k loops.

Version 1

function version1(ary) {
 var newAry = [];
 var iVal, jVal;
 for (var i = 0, il = ary.length; i < il; i++) {
 iVal = ary[i];
 for (var j = ary.length - 1; j >= 0; j--) {
 if (i != j) {
 jVal = ary[j];
 if (iVal[0] == jVal[0] && iVal[1] < jVal[1]) {
 newAry.push(iVal);
 break;
 }
 }
 }
 }
 return newAry;
}

Version 2

function version2(ary) {
 var indices = [];
 var values = [];
 var newAry = [];
 var iVal, 
 index,
 highestFound,
 lowFound;
 for (var i = 0, il = ary.length; i < il; i++) {
 var iVal = ary[i];
 if ((index = indices.indexOf(iVal[0])) == -1) {
 indices.push(iVal[0])
 values.push([ iVal[1] ]);
 index++;
 }
 else {
 values[index].push(iVal[1])
 };
 }
 for (var i = 0, il = values.length; i < il; i++) {
 iVal = values[i];
 highestFound = false;
 for (var j = 0, jl = iVal.length; j < jl; j++) {
 if (!highestFound) {
 lowFound = false;
 for (var k = j + 1, kl = iVal.length; k < kl; k++) {
 if (iVal[j] < iVal[k]) {
 lowFound = true;
 newAry.push([indices[i], iVal[j]]);
 k = kl;
 }
 }
 if (!lowFound) {
 highestFound = true; 
 }
 }
 else {
 newAry.push([indices[i], iVal[j]]);
 }
 }
 }
 return newAry;
}

jsFiddle

jsFiddle with Counters

• McPhelpsius: What purpose is iIsNotMax serving if it doesn't ever evaluate to true?
• Daniel Gimenez: @McPhelpsius Removed that a few minutes ago.
• Daniel Gimenez: @McPhelpsius, Version 2 had a bug when the items weren't sorted. I have since fixed it.

Answer 2

Based on what you've given so far, here's the code I came up with:

var foo = [
 [2, 1],
 [2, 2],
 [2, 3],
 [3, 1],
 [3, 2],
 [4, 1],
 [4, 2],
 [4, 3],
 [4, 4],
 [5, 1],
 [5, 2]
],
 temp = [];
foo.forEach(function (value, index) {
 if (typeof temp[value[0]] === 'undefined') {
 temp[value[0]] = {
 highestValue: value[1],
 position: index
 };
 } else {
 if (temp[value[0]].highestValue < value[1]) {
 temp[value[0]].highestValue = value[1];
 temp[value[0]].position = index;
 }
 }
});
temp.forEach(function(value, index) {
 delete foo[value.position];
});

Do note that if you have in foo for instance [6,1], it will be deleted as well.

Answer 3

Making use of the excellent lodash.js library:

var ary = [ [2,1], [2,2], [2,3], [3,1], [3,2], [4,1], [4,2], [4,3], [4,4], [5,1], [5,2] ];
var results = _(ary)
 // Group by the first value
 .groupBy(function(pair) {
 return pair[0];
 })
 // Turn the groups into arrays
 .map(function(group) {
 // Sort by the second value
 var sorted = _.sortBy(group, function(pair) {
 return pair[1];
 });
 // Keep all but the highest value
 return _.take(sorted, sorted.length-1);
 })
 // Remove the groupings
 .flatten(true)
 // Unwrap the results
 .value();
console.log(results);

jsFiddle: http://jsfiddle.net/dmillz/BhSDT/

I hope that helps!

• McPhelpsius: I probably won't be venturing into a new js library for this. Currently using jQuery and jQMobile. I won't add another library to the mix