Given an array arr of integers, check if there exists two integers N and M such that N is the double of M ( i.e. N = 2 * M).
More formally check if there exists two indices i and j such that :
I have solved this question using nested loops and T/C for the approach is obviously O(n^2). But I have seen the solutions using hashmap or set in Javascript which essentially brings the T/C to O(n). But, I am not getting the intuition behind using a set in this question. How is it relevant? If anyone could explain this, please. Thanks.
You could convert your array to an object or set. Loop through the array, check if element * 2 is in the object/set.
const arr = [1,3,5,7,9,11,14];
const obj = Object.fromEntries(arr.map(el => [el, true])); // O(n)
// obj looks like
//{ "1": true, "3": true, etc}
// loop through arr until we find an element such that twice the element is in obj. Can use O(1) lookups in obj
const result = arr.some(el => obj[el * 2]); // O(n) (usually less)
console.log(result);