Explaining Four Sum Problems

The FourSum method finds all unique quadruplets in the array nums that sum up to the given target. To solve this problem, we use the Two Pointer approach. First, we need to sort the array before implementing the Two Pointer technique.

Example

Let’s consider an example with the array nums = [1, 0, -1, 0, -2, 2] and target = 0.

Sorted Array

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

First Iteration

• i = 0, nums[i] = -2
• j = 1, nums[j] = -1
• low = 2, high = 5
• Sum: -2 + (-1) + 0 + 2 = -1 (less than target, increment low)
• Sum: -2 + (-1) + 0 + 2 = -1 (less than target, increment low)
• Sum: -2 + (-1) + 1 + 2 = 0 (equals target, add [-2, -1, 1, 2] to result)

Second Iteration

• i = 0, nums[i] = -2
• j = 2, nums[j] = 0
• low = 3, high = 5
• Sum: -2 + 0 + 0 + 2 = 0 (equals target, add [-2, 0, 0, 2] to result)

Continue Iterations: The loops continue, skipping duplicates and finding other quadruplets.

public IList<IList<int>> FourSum(int[] nums, int target)
{
    var res = new List<IList<int>>();
    Array.Sort(nums);
    
    for (int i = 0; i < nums.Length - 3; i++)
    {
        if (i > 0 && nums[i] == nums[i - 1])
            continue;

        for (int j = i + 1; j < nums.Length - 2; j++)
        {
            if (j > i + 1 && nums[j] == nums[j - 1])
                continue;

            int low = j + 1;
            int high = nums.Length - 1;

            while (low < high)
            {
                long sum = (long)nums[i] + (long)nums[j] + (long)nums[low] + (long)nums[high];

                if (sum == target)
                {
                    res.Add(new List<int> { nums[i], nums[j], nums[low], nums[high] });
                    
                    while (low < high && nums[low] == nums[low + 1]) low++;
                    while (low < high && nums[high] == nums[high - 1]) high--;
                    
                    low++;
                    high--;
                }
                else if (sum < target)
                {
                    low++;
                }
                else
                {
                    high--;
                }
            }
        }
    }
    
    return res;
}

Sorting the Array

Array.Sort(nums);

The array is sorted to facilitate the two-pointer technique and to easily skip duplicates.

Outer Loop (First Element)

for (int i = 0; i < nums.Length - 2; i++)
{
    if (i > 0 && nums[i] == nums[i - 1]) continue;

The outer loop iterates through the array, selecting the first element of the quadruplet. It skips duplicate elements to avoid duplicate quadruplets.

Second Loop (Second Element)

for (int j = i + 1; j < nums.Length - 1; j++)
{
    if (j > i + 1 && nums[j] == nums[j - 1]) continue;

The second loop selects the second element of the quadruplet. It also skips duplicates.

Two-Pointer Technique (Third and Fourth Elements)

int low = j + 1;
int high = nums.Length - 1;

while (low < high)
{
    long sum = (long)nums[i] + (long)nums[j] + (long)nums[low] + (long)nums[high];
}

The two-pointer technique is used to find the third and fourth elements. The low pointer starts just after the second element, and the high pointer starts at the end of the array.

Checking the Sum

if (sum == target)
{
    res.Add(new List<int> { nums[i], nums[j], nums[low], nums[high] });
    
    while (low < high && nums[low] == nums[low + 1])
        low++;
        
    while (low < high && nums[high] == nums[high - 1])
        high--;
        
    low++;
    high--;
}
else if (sum < target)
{
    low++;
}
else
{
    high--;
}

• If the sum of the four elements equals the target, the quadruplet is added to the result list.
• The low and high pointers are adjusted to skip duplicates and continue searching for other potential quadruplets.
• If the sum is less than the target, the low pointer is incremented to increase the sum.
• If the sum is greater than the target, the high pointer is decremented to decrease the sum.

Returning the Result

return res;

Time Complexity

The time complexity of the FourSum algorithm is,

1. Sorting the Array: (O(nlog n))
2. Nested Loops: The outer two loops run (O(n^2)) times.
3. Two-Pointer Technique: The two-pointer technique runs in (O(n)) time for each pair of the outer loops.

Combining these, the overall time complexity is,

[ O(nlog n) + O(n^3) ]

Since (O(n^3)) dominates (O(n \log n)), the time complexity is,

[ O(n^3) ]

This means the algorithm is cubic in terms of the number of elements in the array, which is efficient for moderate-sized arrays but may become slow for very large arrays.

If you have any more questions or need further assistance, feel free to ask!