3Sum (LeetCode)

Problem Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

• Input: nums = [-1,0,1,2,-1,-4]
• Output: [[-1,-1,2],[-1,0,1]]
• Explanation:
  • nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
  • nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
  • nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
  • The distinct triplets are [-1,0,1] and [-1,-1,2].
  • Notice that the order of the output and the order of the triplets does not matter.

Example 2:

• Input: nums = [0,1,1]
• Output: []
• Explanation: The only possible triplet does not sum up to 0.

Example 3:

• Input: nums = [0,0,0]
• Output: [[0,0,0]]
• Explanation: The only possible triplet sums up to 0.

Constraints

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

Approach

To solve the problem, we can use the two-pointer technique combined with sorting. Here is the step-by-step approach:

1. Sort the Input Array:

   • Sort the array to enable the two-pointer technique and to handle duplicates easily.

2. Iterate Through the Array:

   • Use a loop to fix the first element (i).
   • Use two pointers (j starting from i + 1 and k starting from the end of the array) to find pairs that, along with the element at i, sum to zero.

3. Avoid Duplicates:

   • Skip duplicate elements to avoid duplicate triplets.

4. Calculate and Adjust Pointers:

   • Calculate the sum of the elements at i, j, and k.
   • If the sum is zero, add the triplet to the result and move both pointers.
   • If the sum is greater than zero, move the k pointer left to reduce the sum.
   • If the sum is less than zero, move the j pointer right to increase the sum.

5. Return the Result:

   • Return the list of unique triplets.

Solution Code

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue

            j = i + 1
            k = len(nums) - 1

            while j < k:
                total = nums[i] + nums[j] + nums[k]

                if total > 0:
                    k -= 1
                elif total < 0:
                    j += 1
                else:
                    res.append([nums[i], nums[j], nums[k]])
                    j += 1

                    while j < k and nums[j] == nums[j-1]:
                        j += 1

        return res

JavaScript

var threeSum = function (nums) {
  let res = [];
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

    let j = i + 1;
    let k = nums.length - 1;

    while (j < k) {
      let total = nums[i] + nums[j] + nums[k];

      if (total > 0) {
        k--;
      } else if (total < 0) {
        j++;
      } else {
        res.push([nums[i], nums[j], nums[k]]);
        j++;

        while (j < k && nums[j] === nums[j - 1]) {
          j++;
        }
      }
    }
  }
  return res;
};

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);

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

            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                int total = nums[i] + nums[j] + nums[k];

                if (total > 0) {
                    k--;
                } else if (total < 0) {
                    j++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;

                    while (j < k && nums[j] == nums[j-1]) {
                        j++;
                    }
                }
            }
        }
        return res;
    }
}

C++

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());

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

            int j = i + 1;
            int k = nums.size() - 1;

            while (j < k) {
                int total = nums[i] + nums[j] + nums[k];

                if (total > 0) {
                    k--;
                } else if (total < 0) {
                    j++;
                } else {
                    res.push_back({nums[i], nums[j], nums[k]});
                    j++;

                    while (j < k && nums[j] == nums[j-1]) {
                        j++;
                    }
                }
            }
        }
        return res;
    }
};

Step-by-Step Algorithm

1. Initialize Result List:

   • Create an empty list res to store the triplets whose sum is zero.

   res = []

2. Sort the Input Array :

   • Sort the input array nums in non-decreasing order.

   nums.sort()

3. Iterate Through the Array :

   • Iterate through each element in the sorted array nums.

   for i in range(len(nums)):

4. Skip Duplicate Elements :

   • Check if the current element is a duplicate of the previous element and skip it if it is.

   if i > 0 and nums[i] == nums[i-1]:
       continue

5. Initialize Pointers :

   • Initialize two pointers j and k to point to the elements next to the current element i and at the end of the array, respectively.

   j = i + 1
   k = len(nums) - 1

6. Two-Pointer Approach :

   • Use a two-pointer approach with pointers j and k to find triplets whose sum equals zero.

   while j < k:

7. Calculate Total :

   • Calculate the total sum of the current triplet.

   total = nums[i] + nums[j] + nums[k]

8. Adjust Pointers Based on Total :

   • If the total sum is greater than zero, decrement the k pointer to decrease the total sum.

   if total > 0:
       k -= 1
   • If the total sum is less than zero, increment the j pointer to increase the total sum.

   elif total < 0:
       j += 1
   • If the total sum equals zero, add the triplet [nums[i], nums[j], nums[k]] to the result list res.

   else:
       res.append([nums[i], nums[j], nums[k]])
       j += 1

9. Handle Duplicate Triplets :

   • Increment the j pointer to skip any duplicate elements.

   while j < k and nums[j] == nums[j-1]:
       j += 1

10. Return Result :

    • Return the list res containing all the unique triplets whose sum is zero.

    return res

This algorithm efficiently finds all unique trip

lets in the given array nums whose sum equals zero using a two-pointer approach. It avoids duplicate triplets by skipping duplicate elements during traversal.