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.

• Mast: Does this actually return sets in the format specified? When I test this, the output is on a single line and not in sets.
• iRohitBhatia: @Mast It does. Made it a code snippet
• Mast: Thank you. The output in the snippet puts everything on new lines though, not a line per set as specified.
• iRohitBhatia: @Mast sorry, unable to comprehend what you are saying?

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:

1

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;

¹

• Patrick Roberts: Your hashset approach would yield false positives. Your O(1) check would return true even if c was from the same index of the input array as a or b.
• Sᴀᴍ Onᴇᴌᴀ: @patrickRoberts thanks for the tip - I have updated that section