# C# - O(n^3) - sorted 2 Sum + 2 pointer - key is dupe skip

• do an O(n^2) 2 sum iteration and at each iteration search the remaining array with left and right pointer to find 2 more elements that make up the remaining target. The key is that each time you need to skip over elements that will produce dupes. And because the array has been sorted you can just check if it matches it's previous value to achieve this.

``````    public IList<IList<int>> FourSum(int[] nums, int target) {
IList<IList<int>> lists = new List<IList<int>>();
Array.Sort(nums);

for (int i = 0; i < nums.Length - 3; i++)
{
for (int j = i + 1; j < nums.Length - 2; j++)
{
int left = j + 1;
int right = nums.Length - 1;
while (left < right)
{
int diff = target - nums[i] - nums[j] - nums[left] - nums[right];
if (diff == 0)
{
lists.Add(new List<int>() { nums[i], nums[j], nums[left], nums[right] });

// skip dupes
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;

left++;
right--;
}
else if (diff > 0)
{
left++;
}
else
{
right--;
}
}

// skip dupes
while (j < nums.Length - 3 && nums[j] == nums[j+1]) j++;
}

// skip dupes
while (i < nums.Length - 4 && nums[i] == nums[i+1]) i++;
}

return lists;
}
``````

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