~/leetcode $ 15. 3-Sum

For the brute force method, we can loop through all of the possible triplets in the list using 3 for loops (O(n^3) time) but that would be too inefficient.

When we think about optimising this, we can effectively reduce this to a two sum problem by fixing one of the 3 variables. Let’s say the list is [1, 2, 3, 4, 5]. Then, if we fix index 0 to be the first number, then we are doing two sum on the remaining list ([2, 3, 4, 5]) with the target to be -1 (0 minus the element at index 0). We can solve the reduced two sum using a hashmap in linear time (and using linear space), So overall, this would run in O(n^2) time.

Doing this via two sum is trickier than I initially thought, as I need to return the value (not the index) and I don’t want to have duplicate triplets. So maybe, there are more ways to optimise this…

Initially, I thought of sorting the list before hand and thinking about what that would give me:

• it would get rid of the problem of keeping track of the duplicate (as if we had a duplicate element, they would be next to each other in the list so it would be trivial to check) - we can skip an iteration if the last element was the same as the current element
• let’s say we were still trying to fix the first number, as soon as this number is not negative we can stop (as we want the sum to be equal to 0 and all subsequent numbers would be positive)
• then for our two sum problem, we can do a similar thing where we go through the array (keep a hashset of what we iterated through) but delete the element from the hashset when we use it - this will make sure that we do not get duplicated triplets

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result {};
        sort(nums.begin(), nums.end());

        // fix the first element
        for (int i = 0; i < nums.size() - 2; ++i) {
            // skip duplicate first elements
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }


            // do two sum on the remaining elements
            unordered_map<int, bool> seen {};
            int target = -nums[i];
            for (int j = i + 1; j < nums.size(); ++j) {
                if (seen.contains(target - nums[j])) {
                    // if we haven't used this yet
                    if (!seen[target - nums[j]]) {
                        result.push_back({nums[i], target - nums[j], nums[j]});
                        seen[target - nums[j]] = true;
                    }
                } else {
                    seen[nums[j]] = false;
                }
            }
        }

        return result;
    }
}

Clearly this isn’t good enough so I took a look at what the fast people did and duh you could use two pointers because the list is now sorted… Lemme think…

So I just switched the solution to the two pointer method (input array is sorted) and now we have a very nice space complexity (time complexity O(n^2) - still the same, space complexity O(n^2) -> O(1)).

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result {};
        sort(nums.begin(), nums.end());

        // fix the first element
        for (int i = 0; i < nums.size() - 2; ++i) {
            // skip duplicate first elements
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // do two sum on the remaining elements
            // we can do the sorted version...
            int l = i + 1;
            int r = nums.size() - 1;
            int a = nums[i];
            while (l < r) {
                int b = nums[l];
                int c = nums[r];
                if (a + b + c == 0) {
                    // valid triplet
                    result.push_back({a, b, c});
                    while (l < r && nums[l] == b) {
                        ++l;
                    }
                } else if (a + b + c > 0) {
                    --r;
                } else {
                    ++l;
                }
            }
        }

        return result;
    }
};

Time Complexity: O(n^2)

Space Complexity: O(1)

Time Taken: 26m 42s