18_4Sum.md

18. 4Sum (Medium)

O(N^4) brute force

• using 4 for loops we can solve this question.

Sort + 3ptr + BinarySearch (int overflow)

• TC: O(N^3) - 2loops and finding 2 elements in O(N) time.
• SC: O(N^2) - set of vectors
• we keep i,j,k pointers and find l using binary search.

Sort + 2ptr + BinarySearch

• TC: O(N^3) - 2loops and finding 2 elements in O(N) time.
• SC: O(1)
• we keep i,j pointers and find l and r using binary search.
• We can overcome int overflow by calculating target in every loop.(see code)
• We can also overcome extra space by processing pointers until duplicates occurs.(see code)

Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& num, int target)
    {
        vector<vector<int>> res;
        if (num.empty()) return res;
        int n = num.size();
        sort(num.begin(), num.end());

        for (int i = 0; i < n; i++) {
            int target_3 = target - num[i];
            for (int j = i + 1; j < n; j++) {
                int target_2 = target_3 - num[j];

                int l = j + 1;
                int r = n - 1;
                while (l < r) {
                    int two_sum = num[l] + num[r];
                    if (two_sum < target_2)
                        l++;
                    else if (two_sum > target_2)
                        r--;
                    else {
                        vector<int> quadruplet(4, 0);
                        quadruplet[0] = num[i];
                        quadruplet[1] = num[j];
                        quadruplet[2] = num[l];
                        quadruplet[3] = num[r];
                        res.push_back(quadruplet);

                        // Processing the duplicates of number 3
                        while (l < r && num[l] == quadruplet[2])
                            ++l;
                        // Processing the duplicates of number 4
                        while (l < r && num[r] == quadruplet[3])
                            --r;
                    }
                }
                // Processing the duplicates of number 2
                while (j + 1 < n && num[j + 1] == num[j])
                    ++j;
            }
            // Processing the duplicates of number 1
            while (i + 1 < n && num[i + 1] == num[i])
                ++i;
        }
        return res;
    }
};