Leetcode 3 sum code optimisation 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 &lt; nums.length; i++){
        remainingArr = nums.filter((d,id) =&gt; 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 =&gt; d.split(',')).filter(d =&gt; d.length &gt; 0)
};

var twoSum = function(nums, target, out, seen){
    let myMap = {}
    for(let i = 0; i &lt; 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) =&gt; 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?
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 &lt; nums.length; i++) {
    remainingArr = nums.filter((d, id) =&gt;  id != i);
    twoSum(remainingArr, -nums[i], out, seen);
}
return out.map(d =&gt; d.split(',')).filter(d =&gt; d.length &gt; 0);
};

function twoSum(nums, target, out, seen) {
let myMap = {};
for (let i = 0; i &lt; nums.length; i++) {
    if (myMap[target - nums[i]] != undefined) {
        let val = [target - nums[i], nums[i], -target].sort((a,b) =&gt; 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 &lt; nums.length; i++) {
    remainingArr = nums.filter((d,id) =&gt;  id != i);
    twoSum1(remainingArr, -nums[i], out, seen, myMap);
}
return out.map(d =&gt; d.split(',')).filter(d =&gt; d.length &gt; 0);
};

function twoSum1(nums, target, out, seen, myMap) {
const b = -target;
myMap.clear();
for (let i = 0; i &lt; nums.length; i++) {
    const a = nums[i], idx = target - a;
    if (myMap.has(idx)) {
        let val = [idx, a, b].sort((a,b) =&gt; 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) =&gt; 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 &lt; nums.length) {
    twoSum2(nums.filter((d,id) =&gt;  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 &lt; nums.length; i++) {
    const a = nums[i], idx = target - a;
    if (myMap.has(idx)) {
        if (a &lt; b &amp;&amp; a &lt; idx) { val =  idx &lt; b ? "" + a + idx + b : "" + a + b + idx }
        else if (b &lt; idx) { val =  idx &lt; a ? "" + b + idx + a : "" + b + a + idx }
        else {  val =  a &lt; 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.

threeSum Your original functions with changes unrelated to performance.
threeSum1 Major performance changes
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) =&gt;  id != i);

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

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

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 2........: 1,000,000µs

1 In microseconds µs (One millionth second)
2 time between cycles