Background: I recently worked on a Vue.js project that allows a user to search for a list of municipal services located nearby. When the client handed me the project, I ran a few searches and noticed duplicate entries in the list of results. Sure enough, when I opened the browser console, I saw an error message complaining about duplicate keys in a v-for loop. Since the list comes straight from a GET request to the system backend, I believe a bug in the backend service is responsible for introducing these duplicate items. Another agency wrote the backend code, and we are not sure when we will be able to touch base, so I decided to filter out the duplicates on the front end for the time being. I came up with two approaches. My first approach: The code iterates through the original list of items and adds to a new array any item that does not already exist in the new array.

<template>
  <div>
    <div v-for="result in uniqueResults">
      {{ result }}
    </div>
    ...
  </div>
</template>
<script>
...
computed: {
  uniqueResults() {
    let uniqueItems = [];
    for(var i = 0; i < this.items.length; i++) {
      if (uniqueItems.findIndex((uniqueItem) => uniqueItem.id ===   this.items[i].id) === -1) {
      uniqueItems.push(this.items[i])
      }
    }
    return uniqueItems;
  }
...
</script>

This initial approach worked properly, but slows down the page’s load time. This makes sense, since for every element in the list, we are checking if preceding element is a duplicate. This translates to an asymptotic time complexity of O(n²). I wondered if this could be achieved in linear time. 2. In my second approach, I used Javascript’s Array.prototype.filter() method and took advantage of the second callback parameter, position, to perform deduplication. This code works by returning only the first occurrence of every item and filtering out the rest. The secret sauce is that the method indexOf(foo) returns the index of only the first instance of foo in the array. Although this approach also runs in O(n²) time (since we iterate through every item in the list and indexOf() has a linear time complexity), it actually appears to run faster in practice. Why does this approach run faster? And is there an approach with a better time complexity than O(n^2)?

uniqueResults() {
  return this.items.filter((item, position) =>  (this.items.map(i => i.id).indexOf(item.id) === position));
}

So if for example, an array contains the following values… [{name: Bob, id: 8},{name: Alice, id: 4}, {name: Alice, id: 4}], this maps [8,4,4]. Iterating through the array, the filter function begins at the 0th element. indexOf(8) = 0 so {name: Bob, id: 8} will be included in the result. The filter function then examines the element at index 1. indexOf(4) = 1, so {name: Alice, id: 4} will also be included in the result. Finally, the filter function examines the element at index 2. indexOf(4) = 1 != 2, so the second instance of the object {name: Alice, id: 4} will be filtered out of the result.