15. 3Sum – Solution [Brute-Force to Best]

Here’s the question link on LeetCode 15. 3Sum:

https://leetcode.com/problems/3sum/description

Brute Force O(n³)

The simplest approach is to try every possible combination of three elements.

Use three nested loops, calculate their sum, and if it equals zero, add the triplet to our answer.

But we also need to avoid duplicate triplets. We can sort each triplet and use a set to make sure we only add unique combinations.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();

        set<vector<int>> st;

        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                for(int k = j + 1; k < n; k++) {

                    if(nums[i] + nums[j] + nums[k] == 0) {
                        vector<int> temp = {
                            nums[i], nums[j], nums[k]
                        };

                        sort(temp.begin(), temp.end());
                        st.insert(temp);
                    }
                }
            }
        }

        return vector<vector<int>>(st.begin(), st.end());
    }
};
15. 3Sum Brute force solution

Better O(n²) Sorting + Hash Set

Can we avoid the third loop?

Let’s fix one element and find the other two numbers that add up to its negative.

For example, if the fixed number is -1, we need two numbers whose sum is 1.

We can use a hash set to keep track of numbers we’ve already seen.

For every fixed element:

  1. Calculate the sum we need: target = -nums[i].
  2. Traverse the remaining elements.
  3. Check if target - nums[j] already exists in our hash set.
  4. If yes, we’ve found a triplet!
  5. Otherwise, insert the current number into the set.

We’ll sort the array and use a set of triplets to avoid duplicates.

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

        set<vector<int>> ans;

        int n = nums.size();

        for(int i = 0; i < n; i++) {
            unordered_set<int> seen;

            for(int j = i + 1; j < n; j++) {
                int need = -nums[i] - nums[j];

                if(seen.count(need)) {
                    ans.insert({nums[i], nums[j], need});
                }

                seen.insert(nums[j]);
            }
        }

        return vector<vector<int>>(ans.begin(), ans.end());
    }
};
15. 3Sum Sorting Solution

Optimal O(n²) Two Pointers

Now, can we avoid the hash set too?

Since the array is already sorted, we can use two pointers!

Here’s the idea:

  1. Sort the array.
  2. Fix one element using i.
  3. Place left at i + 1 and right at the end.
  4. Calculate the sum of all three elements.

Now:

  • If the sum is smaller than zero, move left forward to increase the sum.
  • If the sum is greater than zero, move right backward to decrease the sum.
  • If the sum is zero, we’ve found our triplet!

We also need to skip duplicate elements so that we don’t add the same triplet multiple times.

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

        vector<vector<int>> ans;

        int n = nums.size();

        for(int i = 0; i < n - 2; i++) {

            // Skip duplicate first elements
            if(i > 0 && nums[i] == nums[i-1])
                continue;

            int left = i + 1;
            int right = n - 1;

            while(left < right) {

                int sum = nums[i] + nums[left] + nums[right];

                if(sum == 0) {
                    ans.push_back({
                        nums[i], nums[left], nums[right]
                    });

                    left++;
                    right--;

                    // Skip duplicates
                    while(left < right && nums[left] == nums[left-1])
                        left++;

                    while(left < right && nums[right] == nums[right+1])
                        right--;
                }
                else if(sum < 0) {
                    left++;
                }
                else {
                    right--;
                }
            }
        }

        return ans;
    }
};
15. 3Sum Optimal Solution

Leave a Reply