Codewars: Sum Of Pairs

Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.

Source: https://www.codewars.com/kata/sum-of-pairs

The initial problem does seem quite simple:

1. Iterate over the array
2. Check for every item if there is a corresponding pair
3. Return the pair that has the lowest right index

var sum_pairs = function (arr, sum) {
	let pairs = []
	for (let i = 0; i < arr.length; i++) {
		for (let j = 0; j < arr.length; j++) {
			if (arr[i] + arr[j] === sum && i != j && j > i) {
				results.push(j)
			}
		}
	}
	if (results.length) {
		let value = arr[Math.min(...results)]
		return [sum - value, value]
	} else {
		return undefined
	}
}

All Tests pass. You think to yourself, well that was quite straightforward. No big deal. Let’s attempt the solution.

‘Attempt timed out’ solution must finish before 12s pass.

Then let’s optimize the algorithm. what all can we do?

1. We can replace the second loop with the internal array.indexOf Function
2. If we found a match we can stop looking for matches past the matches index
3. We can avoid the pairs array, as we are only interested in a specific pair

var sum_pairs = function (arr, sum) {
	let rightIndex = arr.length
	let match = false
	for (let i = 0; i < rightIndex; i++) {
		let pairIndex = arr.indexOf(sum - arr[i])

		if (pairIndex != -1 && pairIndex < rightIndex && pairIndex !== i) {
			rightIndex = pairIndex
			match = true
		}
	}
	if (match) {
		let value = arr[rightIndex]
		return [sum - value, value]
	}
	return undefined
}

At this point, we only optimized for a couple of edge cases. We did not really reduce the complexity of the algorithm in the worst case every item in the array would need to be compared with every item in the array O(n*n). As even when we are using the internal functions we are still iterating over all items.

Next round of optimizations:

• Instead of iterating and forgetting what we did let’s save our result.

Initially, I had a solution to map all values to an array and then iterate and find the pairs so it would have been O(2*n). But I had difficulties implementing that solution as the array of values could contain duplicates. Then I thought about it and said, hey if I simply compare the current value with the previous values then If I find a match, then I can stop and it would always be the right value. and as a bonus, the complexity is now 0(n), as if the pair is the last two elements of the array we would have needed to visit all elements before that.

var sum_pairs = function (arr, sum) {
    let viewedValues = []
    for (let i = 0; i & lt; arr.length; i++) {
        let currentValue = arr[i];
        let difference = sum - currentValue;
        if (viewedValues[difference]) {
            let result = [difference, currentValue];
            return result;
        }
        viewedValues[currentValue] = true;
    }
    return undefined;
}

comparing the first and the last solution there is a tradeoff between the two solutions.

1. In the 0(n*n) solution it takes longer to get to the result. However, we do not need so much memory.
2. With the O(n) solution, we get the result quicker, but we need a lot more memory.