LeetCode: 4Sum

Solution for LeetCode 4sum

Challenge Description

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution

For time optimization, we need to sort the given array. Then this problem transfered into the 3sum problem,

Time complexity is: $$O(N^3)$$

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > ans;
        sort(num.begin(), num.end());

        if(num.size() < 4) return ans;
        for(size_t first =0; first < num.size() - 3; first++) {
            for(size_t s = first+1; s < num.size()-2; s++) {
              int value = target-num[s]-num[first];
              int head = s + 1;
              int tail = num.size() - 1;
              while(head < tail) {
                int v = num[head] + num[tail];
                if(v == value) {
                  ans.push_back(vector<int> { num[first], num[s], num[head], num[tail] });
                  head++, tail--;
                  while(head < tail && num[head] == num[head-1])
                    head++;
                  while(tail > head && num[tail] == num[tail+1])
                    tail--;

                }
                else if(v > value)
                  tail--;
                else
                  head++;
              }
              while(s < num.size()-2 && num[s+1] == num[s])
                s++;
            }
            while(first < num.size()-3 && num[first] == num[first+1])
                first++;
        }
        return ans;
    }
};

Preparing for an interview? Check out this!

Join my Email List for more insights, It's Free!😋

← Let's LeetCode with Fun Learn from Source Code (an Effec... →