Leetcode three sum in Javascript

Question

I was doing 3sum question 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

For this I wrote the following solution but this is giving me Time Limit Exceeded error.

var threeSum = function(nums) { // Creating triplet memory so there are any duplicates const triplet_memory = {} // num occurrence will have all the numbers in the input array and number of time they occured const num_occurence = {} nums.forEach((element) => { if (!num_occurence.hasOwnProperty(element)) { num_occurence[element] = 1 } else { num_occurence[element] += 1 } }) // iterating over input array nums.forEach((elParent, indexParent) => { // Nested loop so that I try all possible combination nums.forEach((elChild, indexChild) => { if (indexParent !== indexChild) { // decreasing the value of current element from our object // created copied_num_mem so that we don't change main object memeory const copied_num_mem = {...num_occurence} // We are decreasing the elParent and elChild value because for currentSum we are utilizing those value // For example if elParent is 1 and elChild = 2, we would be using those value in our currentSum hence we are decreasing their count by 1 copied_num_mem[elParent] = copied_num_mem[elParent] - 1 copied_num_mem[elChild] = copied_num_mem[elChild] - 1 // multiplying by -1 because suppose we have elParent as -1 and elChild as -1, their sum would give us -2 and we would need the reciprocal of -2 i.e 2 to make it positive const currentSum = (parseInt(elParent) + parseInt(elChild))*-1 // Checking if 2 exist in our copied_num_mem and if yes, it's value is greater than 0 if (copied_num_mem.hasOwnProperty(currentSum.toString()) && copied_num_mem[currentSum.toString()] > 0) { // 2, -1, -1 and -1, 2, -1 all are triplets, we are sorting it so that the order of triplet is always the same and we are going to then store that triplet in our triplet_memory const tripletInt = [currentSum, parseInt(elParent), parseInt(elChild)].sort((a, b) => a -b) const tripletStringified = tripletInt.join('/') triplet_memory[tripletStringified] = true } } }) }) const finalErr = [] Object.keys(triplet_memory).forEach(el => { const elements = el.split('/').map((element) => { return parseInt(element) }) finalErr.push(elements) }) return finalErr }; console.dir(threeSum([0,0,0])) console.dir(threeSum([-1,0,1,2,-1,-4]))

Can someone help me in optimizing the algorithm? I have added comments so it should be easy to understand the code.

Answer 1

Current code

Before discussing the algorithm I want to discuss the current code.

The code currently uses functional approaches - like forEach() methods. This is great for readability but because a function is called for every iteration of each loop, performance can be worse than a regular for loop - e.g. each function adds to the call stack.

The current code also uses hasOwnProperty. For a plain object the in operator could be used since it doesn't matter if the property would be inherited or not.

The last block is this:

const finalErr = [] 

Object.keys(triplet_memory).forEach(el => { const elements = el.split('/').map((element) => { return parseInt(element) }) finalErr.push(elements) }) return finalErr 

It is interesting that there is a .map() call nested inside a .forEach() loop that pushes elements into an array - the latter is the essence of a .map() call. So the .forEach() could be simplified to a .map() call:

return Object.keys(triplet_memory).map(el => { return el.split('/').map((element) => { return parseInt(element) }) }) 

This way there is no need to manually create finalErr, push elements into it and then return it at the end.

Different Algorithm

There are multiple posts about this problem on code review (and SO as well). This buzzfeed article explains multiple approaches including The hash map solution and the two pointer trick, the latter of those two is a great solution.

Two pointer trick

The ‘two pointer trick’ gives a really nice solution to 3sum that doesn’t require any extra data structures. It runs really quickly and some interviewers ‘expect’ this solution (which might be somewhat unfair, but now that you’re seeing it, it’s to your advantage).

For the two pointer solution, the array must first be sorted, then we can use the sorted structure to cut down the number of comparisons we do. The idea is shown in this picture:

vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> output; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { // Never let i refer to the same value twice to avoid duplicates. if (i != 0 && nums[i] == nums[i - 1]) continue; int j = i + 1; int k = nums.size() - 1; while (j < k) { if (nums[i] + nums[j] + nums[k] == 0) { output.push_back({nums[i], nums[j], nums[k]}); ++j; // Never let j refer to the same value twice (in an output) to avoid duplicates while (j < k && nums[j] == nums[j-1]) ++j; } else if (nums[i] + nums[j] + nums[k] < 0) { ++j; } else { --k; } } } return output; 

¹