Leetcode 3 sum code optimisation

Question

I was working on 3sum problem on leetcode

Question

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4]

A solution set is:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

My Solution

var threeSum = function(nums) {
    let out = []
    let seen = {}
    for(let i = 0; i < nums.length; i++){
        remainingArr = nums.filter((d,id) => id != i);
        //Calling twoSum on remaining array
        twoSum(remainingArr, -nums[i], out, seen)
    }
    //Return in expected format by splitting strings and forming arrays
    return out.map(d => d.split(',')).filter(d => d.length > 0)
};

var twoSum = function(nums, target, out, seen){
    let myMap = {}
    for(let i = 0; i < nums.length; i++){
        if(myMap[target - nums[i]] != undefined){
            //If match found convert it to string so that we can test for dupicates
            let val = [target - nums[i], nums[i], -target].sort((a,b) => a - b).join(',');
            //Test for duplicates
            if(!seen[val]) {
                out.push(val)
                seen[val] = true
            }
        }
        myMap[nums[i]] = i;
    }
}

The above solution fails for last 2 very large test cases. For the 2sum implementation I have used the hash map solution rather than 2 pointers.

According to solutions on leetcode I can see the best possible time complexity here is \$O(N^2)\$. But isn't my solution also \$O(N^2)\$ (as i'm using seen map inside the inner loop).

How can I optimize this further?

Answer 1

Performance

This is a performance only review and does not address any styling or composition.

Code examples are focused on performance with no attention given to readability, naming, or re-usability

Time complexity != performance

Time complexity is not a measure of performance. It is a measure of how performance changes as the input size changes.

Two functions can have the same time complexity but very different performance metrics.

---

Improving performance

Looking at your code I see some code that will negatively effect performance.

Your original code cleaned up a little. Semicolons, spaces and the like.

threeSum

function threeSum(nums) {
let out = [];
let seen = {};
for (let i = 0; i < nums.length; i++) {
    remainingArr = nums.filter((d, id) =>  id != i);
    twoSum(remainingArr, -nums[i], out, seen);
}
return out.map(d => d.split(',')).filter(d => d.length > 0);
};

function twoSum(nums, target, out, seen) {
let myMap = {};
for (let i = 0; i < nums.length; i++) {
    if (myMap[target - nums[i]] != undefined) {
        let val = [target - nums[i], nums[i], -target].sort((a,b) => a - b).join(',');
        if (!seen[val]) {
            out.push(val)
            seen[val] = true
        }
    }
    myMap[nums[i]] = i;
}
}

---

Major performance hits

The biggest problem is the line ...

        if (myMap[target - nums[i]] != undefined) {

where the most likely outcome is that myMap[target - nums[i]] is undefined.

Set or Map rather than Object

When JS sees a property name it needs to locate that property.

First it looks at the objects own properties. If that property does not exist, it then starts a recursive search up the prototype chain.

If the result is undefined it will have to have searched all the way up the prototype chain before it can return undefined. As this is the most likely outcome this line adds a lot of additional (under the hood) overhead.

You can use a Set to avoid the need to traverse the prototype chain.

Memory management

There is also an incurred memory overhead because you create and release the object myMap each time the function twoSum is called.

Because javascript does not free up memory until either

• forced to due to low memory,
• or when the code is at idle (Presumably in the leetcode environment that is after the function threeSum has exited and before the result is verified)

All the created myMap slowly eat up memory and will incur a GC (garbage collection) overhead. On a shared environment such as leetcodes cloud processing network memory allocated to a task can be rather small meaning forced GC calls are much more likely.

To avoid memory management overheads reduce the amount of work by reducing the number of new objects created.

In example threeSum1 I moved myMap to the first function and pass it to the second. I clear the map in the second function which is less of a management hit than creating and destroying a new one.

threeSum1

function threeSum1(nums]) {
const out = [];
const seen = new Set();
const myMap = new Set();
for (let i = 0; i < nums.length; i++) {
    remainingArr = nums.filter((d,id) =>  id != i);
    twoSum1(remainingArr, -nums[i], out, seen, myMap);
}
return out.map(d => d.split(',')).filter(d => d.length > 0);
};

function twoSum1(nums, target, out, seen, myMap) {
const b = -target;
myMap.clear();
for (let i = 0; i < nums.length; i++) {
    const a = nums[i], idx = target - a;
    if (myMap.has(idx)) {
        let val = [idx, a, b].sort((a,b) => a - b).join(',');
        if (!seen.has(val)) {
            out.push(val);
            seen.add(val);
        }
    }
    myMap.add(a);
}
}

More info

• MDN Allocations

• MDN Garbage collection

---

Minor improvements

You use Array.sort to sort the 3 values and then Array.join them to get a unique key for the 3 values that sum to 0.

let val = [target - nums[i], nums[i], -target].sort((a,b) => a - b).join(',');

JavaScript's sort knows nothing about the array or why you are sorting it

For 3 items there are only 6 resulting outcomes, requiring at most 4 compares. You don't want the sorted array you just want to know how to build the key.

Building a small string using join is slower than building it manually using concatenation operators.

Thus we can remove the sort and use a set of if, else. and ternaries ? to build the key. No need to swap items in an unneeded array (an array that will use memory management just to exist). No need to use the slow join function to create the key.

Additional improvements.

For the best performance avoid

• Indexing into arrays
• Repeating calculations
• Iterating over arrays more often than needed.
• Manipulating Strings

Final code

Assuming that the order of items in each array in the returned array does not matter, and that the items can be Numbers (not Strings) we can remove the need to map and filler the result.

We store items in vars rather than indexing into the array nums[i] each time we want the value. eg a = nums[i]

We calculate values only once. eg b = -target, idx = target - a

threeSum2

function threeSum2(nums) {
var i = 0;
const out = [], seen = new Set(), map = new Set();
while (i < nums.length) {
    twoSum2(nums.filter((d,id) =>  id != i), -nums[i++], out, seen, map);
}
return out;
};
function twoSum2(nums, target, out, seen, map) {
var val = "", i;
const b = -target;
map.clear();
for (i = 0; i < nums.length; i++) {
    const a = nums[i], idx = target - a;
    if (myMap.has(idx)) {
        if (a < b && a < idx) { val =  idx < b ? "" + a + idx + b : "" + a + b + idx }
        else if (b < idx) { val =  idx < a ? "" + b + idx + a : "" + b + a + idx }
        else {  val =  a < b ? "" + idx + a + b : "" + idx + b + a }
        if (!seen.has(val)) {
            out.push([a, b, idx]);
            seen.add(val);
        }
    }
    map.add(a);
}
}

---

Results

Below are the test results for the 3 functions above.

1. threeSum Your original functions with changes unrelated to performance.
2. threeSum1 Major performance changes
3. threeSum2 Minor performance changes

The first test is on a set of 100 arrays 100 items long with an evenly distributed random set of integers in the range -10000 to 10000

• Note threeSum2 is 5 time faster than original.
• Note threeSum1 is only marginally quicker as the optimizations target only the resulting output data.

Name	Mean time 1	Call per sec	Rel performance	Total time	Calls
threeSum2	1,455.175µs	687	100.00%	1,412ms	970
threeSum1	1,547.062µs	646	94.03%	1,624ms	1,050
threeSum	7,047.454µs	141	20.52%	6,907ms	980

I don`t know the nature of the arrays that leetcode send the function.

The following table shows the result if we focus on the code that creates the result. This is done by reducing the range of values of the input to increase the resulting out array length.

Testing is on a set of 100 arrays 100 items long with an evenly distributed random set of integers in the range -100 to 100

Name	Mean time 1	Call per sec	Rel performance	Total time	Calls
threeSum2	1,904.629µs	525	100.00%	2,000ms	1,050
threeSum1	3,219.081µs	310	59.05%	3,380ms	1,050
threeSum	6,522.878µs	153	29.14%	5,871ms	900

The results show that threeSum2 is the quickest, either by a small or large margin depending on the number of matches found in the input.

Will it pass the leetcode test?

Will it be fast enough to pass the tests? That I do not know as I have not tried this example.

I do know that leetcode test times can swing wildly (from best to worst for the very same code) . Although I do not know as a fact, why, I strongly suspect that run time performance is effected by number of users using the service.

It is my experience (as an .au user) that to get the best results is to use the service in off peek times.

---

More

As i wrote this answer I forget to look into the array you filter

remainingArr = nums.filter((d,id) =>  id != i);

There is opportunity for more optimization in this line worth about ~5% performance increase.

Hints

1. use a Set and remove items using Set.delete tracking removed items, then replace them for the next pass with Set.add You can iterate a set using for (const v of remainingArr) {

2. Or All the filter does is remove one element at the current index from the array. If you passed that index to the second function rather than a filtered array.

Test settings

Test settings. Same for both tests

• Env: Chrome 89.0.4389.90 (64-bit). Laptop Passive cooling (ambient 17.9°)
• Test Cycles.......: 100
• Groups per cycle..: 1
• Calls per group...: 10
• Cool down ²........: 1,000,000µs

¹ In microseconds µs (One millionth second)

² time between cycles