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]

CodePudding user response：

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.

CodePudding user response：

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))

CodePudding user response：

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]]

CodePudding user response：

Just sort the list and remove the duplicates first.
To see this have a look at [1,2,2,3]. Removing the duplicate yields [1,2,3] - duplicate entries generates duplicate results. So just get rid of them in the first place.

If you do not like to modify the input array, just make a copy of it and work on that.

You can also remove all the entries with value greater than the target integer. They will not be part of any solution (I presume only non-negative values, otherwise just skip that part).

Copying an array is in O(n).
Sorting is in O(n log(n)).
Removing duplicates is in O(n).
Removing values greater than target integer is in O(n) (the array is sorted, so start from the end of the array, so really it is in O(m) where m is the number of elements greater than the target integer and depending on your data you might claim that m < n).

You may reduce the input this way and make it easier and faster. On the other hand, you cannot be lower than O(n^2) as far as I can see. You have to loop through the elements and build the pairs.
If you remove the values greater than the target integer beforehand then you can say it is in O((n-m)^2).

It is interesting to pay attention to the efficiency of an algorithm. But sometimes we go too far with wanting to know or to improve the complexity. Ironically by doing this we tend to add complexity to the problem solving.
I'd start with the easiest feasible way. If it works, then great. If there is need for improvement then we can go from there.