CODEWITHSUNDEEP
javascriptarraysindexingduplicates
user4726090
user4726090

Reputation: 27

Javascript get the index of the first and last occurrence of a duplicate element in an array

I have an array of points (lat-long coordinates) some of which are duplicated. For the duplicates, the duplicates would be repeated exactly four times in the array. I would want to know the index of the first and last occurrence of the duplicates in the array. So far, this is what I have done:

I am checking each element with the one next to it (this is an unsorted array)

for(var i = 0; i < points.length; i++) {
  for(var j=i+1; j<points.length; j++) {
    if(points[i] == points[j]) {
      var firstOccurrence = points.indexOf(points[i]);
      var lastOccurrence = points.indexOf(points[i], j+1);
      console.log(firstOccurrence);
      console.log(lastOccurrence);
    }
   }
 }

The firstOccurrence gives the index of the fist Occurrence of a duplicate correctly, but prints the same index four times(may be loops through the for-loop?). The lastOccurrence prints correctly too, but prints the correct index for the first time and a "-1" the remaining three times. What is the mistake I am doing here? I am relatively new to javascript.

EDIT: If I do a 

    if(firstOccurrence) {
      console.log(firstOccurrence); //I would do something else here too apart from printing
    }

It leaves the first occurrence of the first duplicate and prints the remaining indices. For example, if my array was:

 points = [4,4,1,8,0,4,4,5,5,2,7,9,5,5,3,3,10,33,21,3,3];

Then, it prints

   7
   14

leaving out the index of the first occurring duplicate which is 0. Is it because of the j = i+1 in the inner for loop?

Upvotes: 1

Views: 2735

Answers (2)

DanielS
DanielS

Reputation: 774

Here are my two versions of solution: First version is simple to understand, but it prints the duplicates 4 times. Second version uses map reduce like proposed by @Jonah Williams

function printDuplicatesSimple(points) {
    var first, last;
    for (var i = 0; i < points.length; i++) {
        first = points.indexOf(points[i]);
        last = points.lastIndexOf(points[i]);
        print(duplicateToString(first, last));
    }
}

function duplicateToString(first, last) {
    return "(" + first + "," + last + ")";
}

function makeKey(i, arr) {
    var first = points.indexOf(points[i]),
        last = points.lastIndexOf(points[i]);

    return first === last ? -1 : duplicateToString(first, last);
}

function printDuplicatesMapReduce(points) {
    var res = points.reduce(function(dict, currentItem, index, arr) {
        var key = makeKey(index, arr);
        if (key === -1) {
            return dict; //skip
        }
        if (dict.indexOf(key) === -1) {
            dict.push(key);
        }

        return dict;
    }, []);


    print(res);

}

var points = [4, 4, 1, 8, 0, 4, 4, 5, 5, 2, 7, 9, 5, 5, 3, 3, 10, 33, 21, 3, 3];
printDuplicatesSimple(points);

Simple version output: (0,6) (0,6) (2,2) (3,3) (4,4) (0,6) (0,6) (7,13) (7,13) (9,9) (10,10) (11,11) (7,13) (7,13) (14,20) (14,20) (16,16) (17,17) (18,18) (14,20) (14,20)

Map reduce version output: (0,6),(7,13),(14,20)

Upvotes: 0

Jonah Williams
Jonah Williams

Reputation: 21421

An efficient way to find duplicates - without looping through the array for each element - is to find a way to hash your coordinates. You can then use a reducer to group all the indexes for each array, and find your duplicated coordinates easily.

For example, assuming your data looks like this:

var data = [
  {lat: 120, lon: 30},
  {lat: 122, lon: 31},
  {lat: 120, lon: 30},
  ...
];

// Create a function which maps each element to a hashable string

function make(d) {
  return d.lat + ':' + d.lon;
}

// Create a reducer which gathers indexes

// here acc is the accumulated object which starts at {}
// d is each item in the array, and i is the index

data.reduce(function(acc, d, i) {
  var key = make(d);
  acc[key] = acc[key].concat(i) || [i] // gather indexes per element
  return acc;
}, {});

Now you have an object with all the elements of your key value pairs and their index in the original, and unchanged array.

EDIT: in the reduce function I had d instead of key in the acc.

Upvotes: 3

Related Questions