Javascript - Two Sum non-unique elements logic

AwesomeGuy
July 23, 2023
230 views
1 vote
2 Answers

This code works for the test cases having unique elements in the array but not if the same element is present like [3,2,3] so I want something like to add 3+3 === target(when the target is 6) and to get both of their indexes. Please explain me the logic and upto this rate my approach which I used here.

function twoSum(nums, target) {
  return nums.reduce((acc, ele, index) => {
    if (ele + nums.at(index + 1) === target) {
      acc.push(index, index + 1)
    }
    return acc
  }, [])
}

const nums = [2, 7, 11, 15]
const target = 9

console.log(twoSum(nums, target))

const nums1 = [3,2,3]
const target1 = 6

console.log(twoSum(nums1, target1))

Tags: arrays javascript

Answers

Iterate all possible combinations of 2 elements and collect their indices:

function twoSum(nums, target) {
  const result = [];
  for(let i = 0; i < nums.length - 1; i++){
    for(let j = i + 1; j < nums.length; j++){
      if(nums[i] + nums[j] === target){
        result.push([i,j]);
      }
    }
  }
  return result;
}

const log = result => console.log(JSON.stringify(result));

log(twoSum([2, 7, 11, 15], 9))
log(twoSum([2, 7, 11, 7, 15, 2, 7], 9))
log(twoSum([2, 7, 11, 15], 18))
log(twoSum([3, 2, 3], 6))

An Array::reduce() version:

function twoSum(nums, target) {
    return nums.reduce((result, num, i) => {
        return nums.slice(i + 1).reduce((result, num2, j) => {
            num + num2 === target && result.push([i, i + j + 1]);
            return result;
        }, result);
    }, []);
}

const log = result => console.log(JSON.stringify(result));

log(twoSum([2, 7, 11, 15], 9))
log(twoSum([2, 7, 11, 7, 15, 2, 7], 9))
log(twoSum([2, 7, 11, 15], 18))
log(twoSum([3, 2, 3], 6))

Benchmark with a small set:

<script benchmark data-count="1000000">

    // @benchmark mplungjan

    const twoSum2 = (nums, target) => nums.reduce((acc, ele, index) => {
        let complement = target - ele;
        if (acc.map.has(complement)) {
            for (let compIndex of acc.map.get(complement)) {
                acc.result.push([compIndex, index]);
            }
        }
        if (!acc.map.has(ele)) acc.map.set(ele, []);
        acc.map.get(ele).push(index);
        return acc;
    }, { map: new Map(), result: [] }).result;

    // @run
    [twoSum2([2, 7, 11, 15], 9),
    twoSum2([2, 7, 11, 7, 15, 2, 7], 9),
    twoSum2([2, 7, 11, 15], 18),
    twoSum2([3, 2, 3], 6)]


    // @benchmark Alexander

    const twoSum = (nums, target) => {
        const result = [];
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] === target) {
                    result.push([i, j]);
                }
            }
        }
        return result;
    };

    // @run
    [twoSum([2, 7, 11, 15], 9),
    twoSum([2, 7, 11, 7, 15, 2, 7], 9),
    twoSum([2, 7, 11, 15], 18),
    twoSum([3, 2, 3], 6)]

</script>

<script src="https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js"></script>

Benchmark with a big set:

<script benchmark data-count="1">

    const random = Array.from({length:20000}, () => Math.round(Math.random()*20));

    // @benchmark mplungjan

    const twoSum2 = (nums, target) => nums.reduce((acc, ele, index) => {
        let complement = target - ele;
        if (acc.map.has(complement)) {
            for (let compIndex of acc.map.get(complement)) {
                acc.result.push([compIndex, index]);
            }
        }
        if (!acc.map.has(ele)) acc.map.set(ele, []);
        acc.map.get(ele).push(index);
        return acc;
    }, { map: new Map(), result: [] }).result;

    // @run
    twoSum2(random, 9)

    // @benchmark Alexander

    const twoSum = (nums, target) => {
        const result = [];
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] === target) {
                    result.push([i, j]);
                }
            }
        }
        return result;
    };

    // @run
    twoSum(random, 9);

</script>

<script src="https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js"></script>

We can use a map and iterate over the array, storing each element’s value and index. We then check for each element if its complement is already in the map. If found, we iterate over the array of indices for the complement, and for each index, add a pair of indices to the result to handle reuse of a digit.

Time complexity still: O(n)

Due to the possible multiple results, single results are also nested. We can flatten them if you do not like it.

const twoSum = (nums, target) => nums.reduce((acc, ele, index) => {
  let complement = target - ele;
  if (acc.map.has(complement)) {
    for (let compIndex of acc.map.get(complement)) {
      acc.result.push([compIndex, index]);
    }
  }
  if (!acc.map.has(ele)) acc.map.set(ele, []);
  acc.map.get(ele).push(index);
  return acc;
}, { map: new Map(), result: [] }).result;


const nums = [2, 7, 11, 15]
const target = 9
console.log(twoSum(nums, target)) // Output: [0, 1]

const nums1 = [3, 2, 3]
const target1 = 6
console.log(twoSum(nums1, target1)) // Output: [0, 2]

console.log(twoSum([2, 7, 11, 7, 15, 2, 7], 9)) // [[0,1], [0,3], [0,6], [1,5], [3,5], [5,6]]

This one looks more elegant but is O(n^2)

const twoSum = (nums, target) => nums.reduce((acc, ele, i) => {
  nums.slice(i + 1).forEach((ele2, j) => {
    if (ele + ele2 === target) acc.push([i, i + j + 1]);
  });
  return acc;
}, []);

const nums = [2, 7, 11, 15]
const target = 9
console.log(twoSum(nums, target)) // Output: [0, 1]

const nums1 = [3, 2, 3]
const target1 = 6
console.log(twoSum(nums1, target1)) // Output: [0, 2]

console.log(twoSum([2, 7, 11, 7, 15, 2, 7], 9)) // [[0,1], [0,3], [0,6], [1,5], [3,5], [5,6]]

Please signup or login to give your own answer.

Click here to cancel reply.

Javascript – Two Sum non-unique elements logic

Answers