16ms c++ solution with pruning


  • 5
    A

    Sometimes I got 12ms :)

    I just did some pruning when scan through the first two elements. The other 2 elements are determined the same as in 2sum.

    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>>  result;
            if(nums.size() < 4) return result;
            
            vector<int> solution(4,0);
            std::sort(nums.begin(),nums.end());
            int sum,a,b,c,d,Max_d_when_a_increase = nums.size() - 1,Max_d_when_b_increase;
            
            //a,b,c,d are the four index
            //Max_d_when_a_increase is the max possible d when a increase. To have the same sum, when a increase, d can only decrease
            //Max_d_when_b_increase is the max possible d when b increase
            
            for( a = 0; a < Max_d_when_a_increase - 2;a++ )
            {
                //remove dupilcate & do pruning if a too small or too big
                if((a>0 && nums[a] == nums[a-1])
                || nums[a] + nums[Max_d_when_a_increase] + nums[Max_d_when_a_increase-1] + nums[Max_d_when_a_increase-2] < target) continue;
                if(nums[a]+nums[a+1]+nums[a+2]+nums[a+3] > target) break;            
    
                //update Max_d_when_a_increase
                sum = nums[a]+nums[a+1]+nums[a+2];
                while(sum+nums[Max_d_when_a_increase] > target)Max_d_when_a_increase--;
                Max_d_when_b_increase = Max_d_when_a_increase;
    
                solution[0] = nums[a];
                for( b=a+1; b < Max_d_when_b_increase - 1;b++)
                {
                    //remove dupilcate & do pruning if b too small or too big
                    if((b>a+1 && nums[b] == nums[b-1])
                    || nums[a] + nums[b] + nums[Max_d_when_b_increase-1] + nums[Max_d_when_b_increase] < target) continue;
                    sum = nums[a] + nums[b]+nums[b+1];
                    if(sum + nums[b+2] > target) break;
                    
                    //update Max_d_when_b_increase
                    while(sum+nums[Max_d_when_b_increase]>target) Max_d_when_b_increase--;
    
                    solution[1] = nums[b];
                    c = b+1;
                    d = Max_d_when_b_increase;
                    sum = nums[a] + nums[b];
                    while(c < d)//this are the same as two sum
                        if(sum + nums[c] + nums[d] == target)
                        {
                            solution[2]=nums[c];
                            solution[3]=nums[d];
                            result.push_back(solution);
                            
                            do{c++;}while(c < d && nums[c] == nums[c-1]);
                            do{d--;}while(c < d && nums[d] == nums[d+1]);
                        }
                        else if(sum + nums[c] + nums[d] < target) 
                            do{c++;}while(c < d && nums[c] == nums[c-1]);
                        else do{d--;}while(c < d && nums[d] == nums[d+1]);
                }
            }
            return result;
        }
    };

  • 0
    H

    This can be viewed as an improvement of KSum solution (finally based on 2Sum). The improvement is the pruning. But in the worst case, it's the same as KSum, which is O(n3).

    You can try to store all the twoSum pairs. And then use 2Sum method with O(n) using hash. It should be O(n2) time with a lot memory cost. I Wrote one, but the result is worse than KSum solution.


  • 0
    A

    Thanks for the comment.

    In the worst case, there will be O(n3) solutions. (Say the numbers are from 0 - N and our target is 2N). Therefore I believe O(n3) should be the best performance since we at least need to push these many solutions to the memory.

    if you store all the two sum pairs, this step cost O(n2) since you have to go through all the n^2 pairs. And another o(n) or more is required to solve 4sum. So it should be at least O(n3) for the method you mentioned


  • 0
    H

    Thanks for the explanation.

    Find the best performance from the worst solution numbers. This is a great idea. I ignored this part. And for my original O(n2) solution, it's in fact O(n4) solution.


  • 0
    L

    About the duplicate pruning, how to handle the following case:
    {-1,-1,-1,-1,-1,1} target = -5;
    Thank you so much!


Log in to reply
 

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