3Sum medium

Problem Statement

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: Because (-1) + (-1) + 2 = 0, (-1) + 0 + 1 = 0

Example 2

Input: nums = [0,1,1] Output: [] Explanation: There are no triplets that sum to 0.

Steps

1. Sort the array: Sorting the array allows us to efficiently handle duplicates and avoid unnecessary computations.

2. Iterate through the array: We use a three-pointer approach. The outer loop iterates through each element nums[i] as a potential first element of a triplet.

3. Two-pointer technique: For each nums[i], we use two pointers, left and right, to search for the remaining two elements. left starts at i + 1 and right starts at the end of the array.

4. Sum Check: We calculate the sum nums[i] + nums[left] + nums[right].

   • If the sum is 0, we've found a triplet. Add it to the result list, but handle duplicates: increment left and decrement right, and skip over duplicate elements.
   • If the sum is less than 0, we need a larger sum, so increment left.
   • If the sum is greater than 0, we need a smaller sum, so decrement right.

5. Duplicate Handling: After finding a triplet, increment left and decrement right to avoid duplicate triplets. We also skip over duplicate numbers using while loops.

6. Return the Result: The function returns a list of the triplets that sum to 0.

Explanation

The key to solving this problem efficiently is the use of sorting and the two-pointer technique. Sorting allows us to quickly identify duplicates and optimize the search for triplets. The two-pointer approach significantly reduces the time complexity compared to a brute-force approach (which would have a time complexity of O(n³)).

Code

def threeSum(nums):
    """
    Finds all unique triplets in nums that add up to 0.

    Args:
      nums: A list of integers.

    Returns:
      A list of lists, where each inner list is a unique triplet that sums to 0.
    """
    n = len(nums)
    result = []
    nums.sort()  # Sort the array

    for i in range(n - 2):
        # Skip duplicate elements for the first number
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if current_sum == 0:
                result.append([nums[i], nums[left], nums[right]])

                # Skip duplicate elements for the second and third numbers
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1
            elif current_sum < 0:
                left += 1
            else:
                right -= 1

    return result

Complexity

• Time Complexity: O(n²), where n is the length of the input array. This is due to the nested loops and the sorting step (which is O(n log n), but dominated by the nested loops).
• Space Complexity: O(1) (in-place sorting) if we ignore the space used by the output. If we consider the output space, it can be O(n) in the worst case (if there are many triplets).