Most efficient way to compare single array items in JS

Question

I have an array of integers, lets say const foo = [2,5,6,2...]

I would like to create a function that compare all the items and return true if one item is exactly the double of any other, and false if no such case is found.

First idea I had is to do something like

function foo(arr) {
    for(let ind = 0; ind < arr.length; ind++) {
        for( j = 1; j < arr.length; j++) {
        /// CHECK IF ITEM arr[ind] is double of arr[j] or viceversa and return true
        }
    }
    return false
}

This is obviously a pretty bad solution as it goes through each item multiple times. What is the most efficient way for solving this in JS?

You can add a break once you find the result.idk if it works tho always start nested for loop from, value of i — Kanishk Tanwar, Feb 08 '20 at 16:52
@MihaiAlexandru-Ionut of course it is duplicate: with like 100 other questions... — trincot, Feb 08 '20 at 16:54
Possible duplicate [1](https://stackoverflow.com/questions/49215358/checking-for-duplicate-strings-in-javascript-array), [2](https://stackoverflow.com/questions/19901533/i-need-to-check-a-javascript-array-to-see-if-there-are-any-duplicate-values), ...[and more](https://www.google.com/search?q=check+if+array+has+duplicate+javascript+site:stackoverflow.com) — trincot, Feb 08 '20 at 16:55
@trincot, why is this question related to finding duplicates ? Because following example : `[10, 5, 5]` must returns true for this exercise. — Mihai Alexandru-Ionut, Feb 08 '20 at 16:59
People are saying its a duplicate but I still haven't seen a decent answer to this problem..I am trying to find the most efficient way to solve this — greatTeacherOnizuka, Feb 08 '20 at 17:02
@greatTeacherOnizuka, I provided you an answer with complexity of `O(N)`. — Mihai Alexandru-Ionut, Feb 08 '20 at 17:45

score 2 · Answer 1 · answered Feb 08 '20 at 17:15

.map(Number) to convert to Number to make the checks a little easier

.some() will return true if at least one of the entries passes the provided test - That is, does the provided Array .include() a value that is exactly double the current element being tested

const arrayA = ['2','5','6','2'];
const arrayB = ['2','5','4','3'];

function demo (array) {
  return array
    .map(Number)
    .some((ele, _, ori) => ori.includes(ele * 2));
}

console.log(demo(arrayA));
console.log(demo(arrayB));

Could you provide the complexity of your solution ? – Mihai Alexandru-Ionut Feb 08 '20 at 17:18 — Mihai Alexandru-Ionut, Feb 08 '20 at 17:18

Mihai Alexandru-Ionut · Answer 2 · 2020-02-08T17:50:47.953

First of all, you should apply map method with Number constructor in order to obtain one numbers array.

foo = foo.map(Number);

Instead of using two for loops you can just use only one which has O(N) complexity. The idea is that you need to iterate your array and add your current item to a set structure.

Then just check if , at some time, you encountered item * 2 or item/2 using has method of your set structure which has complexity of O(1) conform to this answer.

So, the final complexity is O(n) because we are iterating the array only once. Also, as one alternative, you could use a hash structure which has complexity O(1) for lookup. (hasOwnProperty method.)

myFunction = (arr) => {
  let set = new Set();
  for(i = 0; i < arr.length; i++){
      set.add(arr[i]);    
      if(set.has(arr[i] * 2) || set.has(arr[i]/2))
          return true;
  }
  return false;
}

console.log(myFunction([3,7,6,4, 2]));
console.log(myFunction([1,7,4,5,6]));

Ed Lucas · Answer 3 · 2020-02-08T20:35:33.323

Here's a simple version with a single loop that leverages array.includes(). It exits with a result as soon as one duplicate is found.

const test1 = ['2','3','5','7'];
const test2 = ['2','3','4','8'];

const findDouble = values => {
    for (i = 0; i < values.length; i++) {
        //Convert value to an integer and multiply
        const doubleValue = parseInt(values[i]) * 2;

        // Match using string
        if (values.includes(doubleValue.toString())) {
            return true;
        }
    };
    return false;
}

console.log(findDouble(test1));
console.log(findDouble(test2));

score 0 · Answer 4 · answered Feb 08 '20 at 18:08

Instead of looping twice through the array you want to count the frequency that a number occurs in a single pass. You can achieve that by assigning it to an object where the property key is the number and the value is the frequency of occurrence.

Essentially you want to end up with something like {2:2, 5:1, 6:1 ....}

Then you can use Object.values(obj) to isolate the values and use .include(2) to find if any of those match and return a boolean.

const array = [5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 9]
const arrayTwo = [5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 9, 1, 1]

const exactlyXDupes = (arr,dupe) => {
    return (Object.values(arr.reduce((obj, num) => { obj[num] = (++obj[num] || 1); return obj }, {})).includes(dupe))
}

console.log(exactlyXDupes(array,2))
console.log(exactlyXDupes(arrayTwo,2))

Yash Agarwal · Answer 5 · 2020-02-10T04:28:57.313

You can use JS objects for a bit less time complexity maybe.

You can create an object and while traversing through the input array, keep setting the key corresponding to each value as any non-null value.

After this traverse through this Object's keys and check if for any 'n' in the keys array, Object[2*n] exists.

const foo = ["2", "5", "6", "2", "8", "4"];
const testObj = {};
let flag = 0;
foo.forEach(num => {
  if (testObj[2 * Number(num)]) {  // Test if double element exists already
    flag = 1;
  } else {
    testObj[num] = 1;
  }
});

if (flag !== 1) {
  const keyArray = Object.keys(testObj);
  keyArray.forEach(key => {
    if (testObj[2 * key]) {
      flag = 1;
    }
  });
}
console.log(flag === 1);

Most efficient way to compare single array items in JS

5 Answers5