C++ solution for 4Sum with O(n^3) complexity


  • 0
    A

    Generally a problem statement with 'k'sum results in O(N^k-1) complexity.
    Firstly sort the input array (since time complexity of O(N*logN) doesn't bother here. Then, we shall understand the approach considered to solve our main problem of finding the quad-ripple set when added equates to target.

    We are trying to run two for loops one inside the other (complexity O(n^2) ) to keep track of first and second no's. required for the quad array set.

    Now consider the two pointer concept of an sorted array to find the third and fourth numbers required.

    '''
    class Solution {
    public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(),nums.end());
    set<vector<int> > rs;
    int n=nums.size();
    for(int i=0; i<n-3;i++){
    for(int j=i+1;j<n-2;j++){
    int p=j+1;
    int q=n-1;
    while(p<q){
    int sum= nums[i]+nums[j]+nums[p]+nums[q];
    if(sum==target){
    vector<int> temp(4);
    temp[0] = nums[i];
    temp[1] = nums[j];
    temp[2] = nums[p];
    temp[3] = nums[q];
    rs.insert(temp);
    p++;
    q--;
    }else if(sum<target){
    p++;
    }else{
    q--;
    }
    }
    }
    }
    vector<vector<int> > result(rs.begin(),rs.end());
    return result;
    }
    };
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.