Discovering repeated arrays within an array

Question

Discovering repeated arrays within an array

Given a nested array, what is the best approach to finding duplicates efficiently?

var array = [
  [
    11.31866455078125,
    44.53836644772605
  ],
  [                     // <-- Here's the duplicate
    11.31866455078125,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.50140292110874
  ]
]

While using lodash, I have managed to get the unique elements by utilizing _.uniqWith and _.isEqual:

_.uniqWith(array, _.isEqual)

This code returns:

[ 
    [ 11.31866455078125,  44.53836644772605 ],
    [ 11.371536254882812, 44.53836644772605 ],
    [ 11.371536254882812, 44.50140292110874 ]
]

However, instead of just obtaining the unique items, my goal is to locate the duplicated element and ideally determine the index of its first occurrence.

I am wondering if there is a method within the lodash library that can help achieve this task, or if manual comparison through loops is necessary. Any insights would be appreciated.

My current constraints prevent me from rewriting functions, so I am exploring options such as:

Finding only the duplicate element or noting the difference between it and the "unique list".
Identifying the index of an array within another array, possibly with filtering and reducing once the duplicate item is found using _.isEqual.

In addition, I am aiming to avoid creating separate objects like Hash/Map to count occurrences of keys and prefer a functional approach that does not necessitate additional data structures.

javascript arrays underscore.js lodash

Answer 1

Answer №1

Utilizing Lodash provides a plethora of helpful functions for easily identifying the first occurrence of a duplicate index.
By utilizing the _.findIndex() and _.isEqual() methods, you can utilize the following code snippet to pinpoint the initial duplicate index:

var firstDuplicate = _.findIndex(array, function(value, index, collection) {
  var checkEquality = _.isEqual.bind(undefined, value);
  return _.findIndex(collection.slice(0, index), checkEquality) !== -1;
});

Alternatively, for slightly improved performance but increased verbosity, consider this approach:

var firstDuplicate = _.findIndex(array, function(value, index, collection) {
  var checkEquality = _.isEqual.bind(undefined, value);
  return _.findIndex(collection, function(val, ind) {
     return ind < index && checkEquality(val);
  }) !== -1;
});

If no duplicates are found, the function will return -1. This algorithm essentially scans through the array and checks if the current element has already occurred earlier in the sequence. If it has, the function immediately returns the index of that duplicate element.
Feel free to explore the operational demo.

Answer 2

Utilizing Lodash provides a plethora of helpful functions for easily identifying the first occurrence of a duplicate index.
By utilizing the _.findIndex() and _.isEqual() methods, you can utilize the following code snippet to pinpoint the initial duplicate index:

var firstDuplicate = _.findIndex(array, function(value, index, collection) {
  var checkEquality = _.isEqual.bind(undefined, value);
  return _.findIndex(collection.slice(0, index), checkEquality) !== -1;
});

Alternatively, for slightly improved performance but increased verbosity, consider this approach:

var firstDuplicate = _.findIndex(array, function(value, index, collection) {
  var checkEquality = _.isEqual.bind(undefined, value);
  return _.findIndex(collection, function(val, ind) {
     return ind < index && checkEquality(val);
  }) !== -1;
});

If no duplicates are found, the function will return -1. This algorithm essentially scans through the array and checks if the current element has already occurred earlier in the sequence. If it has, the function immediately returns the index of that duplicate element.
Feel free to explore the operational demo.

Answer 3

Answer №2

One way to solve this problem is by utilizing the uniqWith() function along with difference():

_.indexOf(array, _.head(_.difference(array, _.uniqWith(array, _.isEqual))));

The steps involved are as follows:

Apply uniqWith() to eliminate duplicates from the original array.
Utilize difference() to compare the original array with the duplicate-free version, resulting in an array of duplicates.
Use head() to extract the first item from the duplicated items list.
Finally, employ indexOf() to determine the index of the duplicate, which happens to be 1 in this case.

If the goal is to find the index of the initial value rather than its duplicate, some modifications are necessary:

var duplicate = _.head(_.difference(array, _.uniqWith(array, _.isEqual)));
_.findIndex(array, _.unary(_.partial(_.isEqual, duplicate)));

In this revised approach, we still utilize both uniqWith() and difference() to identify the duplicate element. However, findIndex() is used to locate the index. This adjustment is made because we need to pinpoint the position of the original duplicate rather than the repeated one. By constructing the predicate using partial() and unary(), the outcome is now 0.

Answer 4

One way to solve this problem is by utilizing the uniqWith() function along with difference():

_.indexOf(array, _.head(_.difference(array, _.uniqWith(array, _.isEqual))));

The steps involved are as follows:

Apply uniqWith() to eliminate duplicates from the original array.
Utilize difference() to compare the original array with the duplicate-free version, resulting in an array of duplicates.
Use head() to extract the first item from the duplicated items list.
Finally, employ indexOf() to determine the index of the duplicate, which happens to be 1 in this case.

If the goal is to find the index of the initial value rather than its duplicate, some modifications are necessary:

var duplicate = _.head(_.difference(array, _.uniqWith(array, _.isEqual)));
_.findIndex(array, _.unary(_.partial(_.isEqual, duplicate)));

In this revised approach, we still utilize both uniqWith() and difference() to identify the duplicate element. However, findIndex() is used to locate the index. This adjustment is made because we need to pinpoint the position of the original duplicate rather than the repeated one. By constructing the predicate using partial() and unary(), the outcome is now 0.

Answer 5

Answer №3

If you want to identify duplicates in an array, you can achieve this easily using plain JavaScript. Here is my approach:

for (let i = 0; i < array.length; i++) {
  for (let j = i + 1; j < array.length; j++) {

     // Compare sub-array lengths for quick elimination
     if (array[i].length !== array[j].length) {
        continue;
     }
     
     // Check for duplicate elements
     var dupe = true;
     for (var k = 0; k < array[i].length; k++) {
       if (array[i][k] !== array[j][k]) {
         dupe = false;
         break;
       }
     }
     
     // Print if a duplicate is found
     if (dupe) {
         console.debug("%d is a dupe", j); 
     }
   }
 }

A great feature of this implementation is that it will notify you multiple times if an array at a certain index is a duplicate for various duplicates, allowing you to track the duplicates at each index!

This method is highly efficient as the inner for loop (j) always starts from the next position of the outer loop (i), reducing the number of checks needed.

You can also check out a live demo on Plunker

Answer 6

If you want to identify duplicates in an array, you can achieve this easily using plain JavaScript. Here is my approach:

for (let i = 0; i < array.length; i++) {
  for (let j = i + 1; j < array.length; j++) {

     // Compare sub-array lengths for quick elimination
     if (array[i].length !== array[j].length) {
        continue;
     }
     
     // Check for duplicate elements
     var dupe = true;
     for (var k = 0; k < array[i].length; k++) {
       if (array[i][k] !== array[j][k]) {
         dupe = false;
         break;
       }
     }
     
     // Print if a duplicate is found
     if (dupe) {
         console.debug("%d is a dupe", j); 
     }
   }
 }

A great feature of this implementation is that it will notify you multiple times if an array at a certain index is a duplicate for various duplicates, allowing you to track the duplicates at each index!

This method is highly efficient as the inner for loop (j) always starts from the next position of the outer loop (i), reducing the number of checks needed.

You can also check out a live demo on Plunker

Answer 7

Answer №4

If you're unsure how to tackle this problem, your best bet might be to construct the algorithm yourself. While neither this solution nor the alternatives mentioned are extremely efficient, they should get the job done:

function findIndex(array, startingIndex, value) {
  var predicate = _.partial(_.isEqual, value);
  var arraySubset = array.slice(startingIndex+1);
  var index = arraySubset.findIndex(predicate);
  return index === -1 ? index : index+startingIndex+1;
}

function findDuplicates(array) {
  return array.map((value, index) => {
    return {
      value,
      index: findIndex(array, index, value)
    };
  }).filter(info => info.index !== -1);
}

findDuplicates([1, 2, 3, 4, 1, [ 3 ], [ 4 ], [ 3 ] ]);

// [ { value: 1, index: 4 }, { value: [ 3 ], index: 7 } ]    // [ { value: 1...

This strategy involves mapping out the array, using .findIndex() on the remaining items in the array, recording the index of any duplicates, and providing details about each item with a duplicate along with the duplicate's index.

An advantage of this approach is that it can handle triplicates or any number of repetitions of a value.

Answer 8

If you're unsure how to tackle this problem, your best bet might be to construct the algorithm yourself. While neither this solution nor the alternatives mentioned are extremely efficient, they should get the job done:

function findIndex(array, startingIndex, value) {
  var predicate = _.partial(_.isEqual, value);
  var arraySubset = array.slice(startingIndex+1);
  var index = arraySubset.findIndex(predicate);
  return index === -1 ? index : index+startingIndex+1;
}

function findDuplicates(array) {
  return array.map((value, index) => {
    return {
      value,
      index: findIndex(array, index, value)
    };
  }).filter(info => info.index !== -1);
}

findDuplicates([1, 2, 3, 4, 1, [ 3 ], [ 4 ], [ 3 ] ]);

// [ { value: 1, index: 4 }, { value: [ 3 ], index: 7 } ]    // [ { value: 1...

This strategy involves mapping out the array, using .findIndex() on the remaining items in the array, recording the index of any duplicates, and providing details about each item with a duplicate along with the duplicate's index.

An advantage of this approach is that it can handle triplicates or any number of repetitions of a value.

Answer 9

Answer №5

In my opinion, the creation of a Lookup Table (LUT) stands out as an incredibly effective technique for conducting comparisons. This particular approach involves generating a LUT using Array.prototype.reduce(), subsequently altering the original array to eliminate not just one but all instances of duplicate elements regardless of quantity.

var arr = [
  [
    11.31866455078125,
    44.53836644772605
  ],
  [
    11.31866455078125,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.50140292110874
  ]
];
arr.reduce((p,c,i)=> { var prop = c[0]+"" + c[1]+""; 
                       p[prop] === void 0 ? p[prop] = i : p.dups.push(i);
                       return p;
                     },{dups:[]}).dups.reverse().forEach( i => arr.splice(i,1))

document.write('<pre>' + JSON.stringify(arr, 0, 2) + '</pre>');

Nevertheless, opting for creating a new array while retaining the original would undeniably lead to a significantly speedier process.

Answer 10

In my opinion, the creation of a Lookup Table (LUT) stands out as an incredibly effective technique for conducting comparisons. This particular approach involves generating a LUT using Array.prototype.reduce(), subsequently altering the original array to eliminate not just one but all instances of duplicate elements regardless of quantity.

var arr = [
  [
    11.31866455078125,
    44.53836644772605
  ],
  [
    11.31866455078125,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.50140292110874
  ]
];
arr.reduce((p,c,i)=> { var prop = c[0]+"" + c[1]+""; 
                       p[prop] === void 0 ? p[prop] = i : p.dups.push(i);
                       return p;
                     },{dups:[]}).dups.reverse().forEach( i => arr.splice(i,1))

document.write('<pre>' + JSON.stringify(arr, 0, 2) + '</pre>');

Nevertheless, opting for creating a new array while retaining the original would undeniably lead to a significantly speedier process.

Discovering repeated arrays within an array

Answer №1

Answer №2

Answer №3

Answer №4

Answer №5

Similar questions

What is the process for executing a Js file on a website?

What is the best way to assign user input to my JavaScript variables?

Understanding array manipulation in a Jade file using Node.js

ng-repeat to display items based on dropdown choice or user's search input

"Enhanced visuals with parallax scrolling feature implemented on various sections for an engaging

Retrieving POST request headers in Nightmare JS following a click() function execution and a wait() function delay

Finding a potential data breach in Node.js, MongoDB, and Chrome, exposed passwords are

Add a user to a guild using Discord API

Passing an event from a Vue3 parent component to its child component

Working with AngularJS: Accessing a JSON file from the local directory

Can someone assist me in understanding the proper syntax for the Node.js function that inserts a document into Watson's Discovery service from the watson-developer-cloud library?

Error: Node-Sass - Unable to download win32-x64-57_binding.node

Learn the steps for inserting or updating data in a local JSON file solely through JavaScript

Vue.js methods bound as properties on a parent object

What is the syntax for declaring a boolean or object type?

Arranging array elements according to the values in another array

Encountering difficulties displaying a webpage in Express.js following a successful DELETE request

I'm still searching for a proper solution on how to access JavaScript/jQuery functions within Colorbox

What is the method for creating an array of strings in VueJS?

The dropdown list event does not seem to be triggering when JavaScript is implemented