Leetcode three sum in Javascript

Question 1

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 meTime 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.

Question 2

Does this actually return sets in the format specified? When I test this, the output is on a single line and not in sets.

Question 3

@Mast It does. Made it a code snippet

Question 4

Thank you. The output in the snippet putseverything on new lines though, not a line per set as specified.

Question 5

@Mast sorry, unable to comprehend what you are saying?

Question 6

Current code

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

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

The current code also useshasOwnProperty. For a plain object thein 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 createfinalErr, push elements into it and then return it at the end.

Different Algorithm

There aremultiple posts about this problem on code review (andSO as well). This buzzfeed article explains multiple approaches includingThe hash map solution andthe 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;

¹

Question 7

Your hashset approach would yield false positives. Your O(1) check would return true even ifc was from the same index of the input array asa orb.

Question 8

@patrickRoberts thanks for the tip - I have updated that section

Sᴀᴍ Onᴇᴌᴀ♦ 29.6k16 gold badges46 silver badges203 bronze badges · Answer 1 · 2020-07-06 21:14:23Z

Current code

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

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

The current code also useshasOwnProperty. For a plain object thein 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 createfinalErr, push elements into it and then return it at the end.

Different Algorithm

There aremultiple posts about this problem on code review (andSO as well). This buzzfeed article explains multiple approaches includingThe hash map solution andthe 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;

¹

Your hashset approach would yield false positives. Your O(1) check would return true even ifc was from the same index of the input array asa orb.
@patrickRoberts thanks for the tip - I have updated that section

Movatterモバイル変換

Stack Exchange Network

Leetcode three sum in Javascript

Question

My solution

1 Answer1

Current code

Different Algorithm

Two pointer trick

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS