Post
Ask Question

Explaining 3SUM Problem

The 3 Sum problem is a classic algorithmic challenge. The task is to find all unique triplets in an array of integers that add up to zero.

Here is the Wikipedia link - 3SUM

Problem Statement

Find all unique triplets in the array that sum up to zero.

Example

Consider the array: nums = [-1, 0, 1, 2, -1, -4].

Step-by-Step Solution to 3SUM Problem

  1. Sorting the Array: First, sort the array to make it easier to handle duplicates and use the two-pointer technique.

    Array.Sort(nums); // nums = [-4, -1, -1, 0, 1, 2]

  2. Iterating through the Array: Use a loop to iterate through each element of the array.

    for (int i = 0; i < n - 2; i++)

  3. Skipping Duplicates: Skip duplicate elements to avoid repeated triplets.

    if (i > 0 && nums[i] == nums[i - 1])
    continue;

  4. Two-Pointer Technique: Use two pointers, left and right, to find pairs that sum to the negative of the current element nums[i].

    int left = i + 1, right = n - 1;

  5. Finding Triplets: Use a while loop to find pairs that sum to the negative of nums[i].

    while (left < right)
{
    int sum = nums[i] + nums[left] + nums[right];

    if (sum == 0)
    {
        res.Add(new List<int> { nums[i], nums[left], nums[right] });
        while (left < right && nums[left] == nums[left + 1]) { left++; }
        while (left < right && nums[right] == nums[right - 1]) { right--; }
        left++;
        right--;
    }
    else if (sum < 0)
    {
        left++;
    }
    else
        right--;
}

Detailed Example Walkthrough

  1. Initial Array: [-4, -1, -1, 0, 1, 2]

  2. First Iteration (i = 0):

    • nums[i] = -4
    • left = 1, right = 5
    • Calculate sum = -4 + (-1) + 2 = -3 (sum < 0, move left to 2)
    • Calculate sum = -4 + (-1) + 2 = -3 (sum < 0, move left to 3)
    • Calculate sum = -4 + 0 + 2 = -2 (sum < 0, move left to 4)
    • Calculate sum = -4 + 1 + 2 = -1 (sum < 0, move left to 5)
    • End of this iteration as left is not less than right.

  3. Second Iteration (i = 1):

    • nums[i] = -1
    • left = 2, right = 5
    • Calculate sum = -1 + (-1) + 2 = 0 (sum == 0, add [-1, -1, 2] to result)
    • Skip duplicates: move left to 3, move right to 4
    • Calculate sum = -1 + 0 + 1 = 0 (sum == 0, add [-1, 0, 1] to result)
    • Skip duplicates: move left to 4, move right to 3
    • End of this iteration as left is not less than right.

  4. Third Iteration (i = 2):

    • nums[i] = -1 (skip as it’s a duplicate of nums[i-1])

  5. Fourth Iteration (i = 3):

    • nums[i] = 0
    • left = 4, right = 5
    • Calculate sum = 0 + 1 + 2 = 3 (sum > 0, move right to 4)
    • End of this iteration as left is not less than right.
public IList<IList<int>> ThreeSum(int[] nums)
{
    var res = new List<IList<int>>();
    Array.Sort(nums);
    int n = nums.Length;

    for (int i = 0; i < n - 2; i++)
    {
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        int left = i + 1, right = n - 1;

        while (left < right)
        {
            int sum = nums[i] + nums[left] + nums[right];

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

Result

The unique triplets that sum to zero are:

res = [[-1, -1, 2], [-1, 0, 1]]

Time Complexity

  • Sorting the Array: O(n log n)
  • Outer Loop: O(n)
  • Two-Pointer Technique: O(n) for each iteration of the outer loop

Overall time complexity: O(n²).


Similar Articles