0

I am trying to solve the question,

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

I think I have understood the logic that I need to implement, but my code it is not giving the desired output.

Example: Input: [-3,-2,-1,0,0,1,2,3], 0

The expected output is:

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

but my code outputs this:

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

My C++ Code below:

class Solution {

public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n=nums.size();
        vector<vector<int>> ans;
        int low;
        int high;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-2;i++)
        {
            for(int j=i+1;j<n-1;j++)
            {
                low=j+1;
                high=n-1;
                int req=target-(nums[i]+nums[j]);
                while(low<high)
                {
                    if(nums[low]+nums[high]==req)
                    {
                 ans.push_back({nums[i],nums[j],nums[low],nums[high]});
                     while(high>low && nums[high-1]==nums[high])
                         --high;
                     while(high>low && nums[low+1]==nums[low])
                         ++low;
                        break;
                    }
                    else if(nums[low]+nums[high]>req)
                    {
                        high--;
                    }
                    else
                        low++;
                }
                while(j+1<n && nums[j]==nums[j+1])
                    ++j;
                while(i+1<n && nums[i]==nums[i+1])
                    ++i;
            }
        }
        return ans;
    }
};

Where is the mistake?

David
  • 4,514
  • 2
  • 32
  • 39
  • 1
    Since you know the input that leads to the wrong output, it should be easy to create a [mre], build it locally, and then [*debug*](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) the program. Also see [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Some programmer dude May 12 '22 at 05:58
  • 1
    This seems not to be the most straight forward solution, which probably is correct, in order to avoid TLE. But it would be interesting if simplifying gets you better results. Make a few steps towards brute force, not for the final version, but to get the concept right at first. Then optimise. – Yunnosch May 12 '22 at 06:02
  • *Where is the mistake?* -- Just to let you know, the responsibility is on you to tell us where the mistake *may* be - debugging is part of learning how to write programs. How to correct the mistake is a different issue, but at the very least, you're responsible in knowing the rough location of the mistake. This requires you to debug your code, and then post your observations you find when you debugged your code. Too many new posters post code that doesn't work, and then sit back and wait for someone else here to debug the code. It doesn't or shouldn't work that way. – PaulMcKenzie May 12 '22 at 06:20
  • As a side node, fewer blank lines would make it easier to see the structure. Use a few to help with seeing structure, but get rid of most. – Yunnosch May 12 '22 at 06:26
  • To yourself and us other users, please explain in prose the idea of your loop structure. For "brute force" I would expect four nested self-similar loops with a single `if`. Explain your approach, the differences of your code to the brute force attempt. – Yunnosch May 12 '22 at 06:28
  • 1
    You assume that, for a given `i` and `j`, there could only be one pair adding up to `target-(nums[i]+nums[j])`. This is obviously not true, as witnessed by `[-3,0,0,3]` and `[-3,0,1,2]`. You break out of `while(low – Igor Tandetnik May 15 '22 at 03:17

0 Answers0