Skip to main content
Code Review

Return to Answer

deleted 1236 characters in body
Source Link
Sᴀᴍ Onᴇᴌᴀ ♦
Sᴀᴍ Onᴇᴌᴀ ♦
  • 28.5k
  • 16
  • 45
  • 192

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;

1

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;

1

deleted 1236 characters in body
Source Link
Sᴀᴍ Onᴇᴌᴀ ♦
Sᴀᴍ Onᴇᴌᴀ ♦
  • 28.5k
  • 16
  • 45
  • 192

There are multiple posts about this problem on code review (and SO as well). One review of a implementation by Emily L. suggests an algorithm with \$O(n^2)\$ time complexity.

Better algorithm

We can easily reach O(n^2) time complexity.

We need to find all a, b, c such that a+b+c=0. Note that this is equivalent to c = -(a+b). Hence if we can check if c exists in the input in O(1) time, then we just need to try each pair of a and b and see if a matching c exists. Since there are O(n^2) pairs we have O(n^2*1) time.

A hash set provides the necessary O(1) check if c is present in the input.

(I'm not going to handle the three zeros, you can figure that out).

Pseudocode:

unordered_map<int> hashset;

for(auto& x : input){ hashset.put(x); }

for(int i = 0; i < input.size(); ++i){ 

    for(int j = i+1; j < input.size(); j++){
        auto c = -(input[i] + input[j]);
        if(hashset.contains(c)){
            output.addTuple(input[i], input[j], - c);
        }
    }
}

A similar approach could be takenThis buzzfeed article explains multiple approaches including - with JS an object likeThe hash map solution and num_occurrence could be used for the hashsetthe two pointer trick, but it wouldn't need to count the numberlatter of occurrences. Alternativelythose two is a Set could be used with the .has() method for checking if an element exists in the setgreat solution.

There are multiple posts about this problem on code review (and SO as well). One review of a implementation by Emily L. suggests an algorithm with \$O(n^2)\$ time complexity.

Better algorithm

We can easily reach O(n^2) time complexity.

We need to find all a, b, c such that a+b+c=0. Note that this is equivalent to c = -(a+b). Hence if we can check if c exists in the input in O(1) time, then we just need to try each pair of a and b and see if a matching c exists. Since there are O(n^2) pairs we have O(n^2*1) time.

A hash set provides the necessary O(1) check if c is present in the input.

(I'm not going to handle the three zeros, you can figure that out).

Pseudocode:

unordered_map<int> hashset;

for(auto& x : input){ hashset.put(x); }

for(int i = 0; i < input.size(); ++i){ 

    for(int j = i+1; j < input.size(); j++){
        auto c = -(input[i] + input[j]);
        if(hashset.contains(c)){
            output.addTuple(input[i], input[j], - c);
        }
    }
}

A similar approach could be taken - with JS an object like num_occurrence could be used for the hashset, but it wouldn't need to count the number of occurrences. Alternatively a Set could be used with the .has() method for checking if an element exists in the set.

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.

Source Link
Sᴀᴍ Onᴇᴌᴀ ♦
Sᴀᴍ Onᴇᴌᴀ ♦
  • 28.5k
  • 16
  • 45
  • 192

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). One review of a implementation by Emily L. suggests an algorithm with \$O(n^2)\$ time complexity.

Better algorithm

We can easily reach O(n^2) time complexity.

We need to find all a, b, c such that a+b+c=0. Note that this is equivalent to c = -(a+b). Hence if we can check if c exists in the input in O(1) time, then we just need to try each pair of a and b and see if a matching c exists. Since there are O(n^2) pairs we have O(n^2*1) time.

A hash set provides the necessary O(1) check if c is present in the input.

(I'm not going to handle the three zeros, you can figure that out).

Pseudocode:

unordered_map<int> hashset;

for(auto& x : input){ hashset.put(x); }

for(int i = 0; i < input.size(); ++i){ 

    for(int j = i+1; j < input.size(); j++){
        auto c = -(input[i] + input[j]);
        if(hashset.contains(c)){
            output.addTuple(input[i], input[j], - c);
        }
    }
}

A similar approach could be taken - with JS an object like num_occurrence could be used for the hashset, but it wouldn't need to count the number of occurrences. Alternatively a Set could be used with the .has() method for checking if an element exists in the set.