I am trying to write a function that will take an array and a target integer. As result, I want to return all possible pairs, which the sum of the pair is less than the target integer. The result should avoid duplicates. For example:[2,4] and [4,2] are the same.
Example: Input:[1,2,2,3,4,5], 6 Output:[[1,2],[1,3],[1,4],[2,2]]
Below is what I can think of, but the problem is that it will have duplicates, and also it is nested loop which has n square for big O in terms of time complexity. Is there a better solution? and how can I get rid of duplicates?
function twoNumSum(array, targetNum) {
let result = [];
for (i = 0; i < array.length; i++) {
for (j = i + 1; j < array.length; j++) {
if (array[i] + array[j] < targetNum) {
if (!result[(array[i], array[j])]) {
result.push([array[i], array[j]]);
}
}
}
}
return result;
}
//Test for my solution
console.log(twoNumSum([1, 2, 3, 4], 4));//output=[1,2]
console.log(twoNumSum([1, 2, 3], 3)),6//output=[]
console.log(twoNumSum([1, 2, 2, 3, 4], 5));//output=[[1,2],[1,2],[1,3],[2,2] DUPLICATES of [1,2]
Consider the scenario where each possible pair in the array has a sum less than the target (something like [1,2,3,4], target=10). There are n^2 valid pairs, so your time complexity is unlikely to get better than O(n^2).
For handling duplicates, you could order the pairs like [smaller element, bigger element] and store the pairs in a set.
you can slightly modify your implementation using Set, JSON.stringify and JSON.parse
Set ensure that you don't have duplicates but in order to do that on an array I converted it into a json string.
When you have your unique values you can transform the Set in an array and parse the json string back into an array
function twoNumSum(array, targetNum) {
let result = new Set();
for (i = 0; i < array.length; i++) {
for (j = i + 1; j < array.length; j++) {
if (array[i] + array[j] < targetNum) {
result.add(JSON.stringify([array[i], array[j]]));
}
}
}
return [...result].map(JSON.parse);
}
//Test for my solution
console.log(twoNumSum([1, 2, 2, 3, 4], 6))To avoid duplicates, I've used Object instead of Array to store pairs
Before Adding a pairs, Check first if pairs not in object keys
!(pairs.toString() in result)
I used two loops, the second start from the next of the current index i (to avoid comparing the first pair with itself)
for (let j = i + 1; j < array.length - i - 1; j++)
function twoNumSum(array, targetNum) {
let result = {};
for (i = 0; i < array.length; i++) {
const currNumber = array[i];
for (let j = i + 1; j < array.length - i - 1; j++) {
const nextNumber = array[j];
const pairs = [currNumber, nextNumber];
const innserSum = pairs[0] + pairs[1];
if (innserSum < targetNum && !(pairs.toString() in result)) {
result[pairs] = pairs;
}
}
}
return Object.values(result);
}
console.log(JSON.stringify(twoNumSum([1, 2, 2, 3, 4], 6))); //[[1,2],[1,3],[2,2]]