Leetcode 15 - 3Sum

Table of contents

Problem

Given an integer array nums, the task is to return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. It is important to note 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:
The distinct triplets are [-1,0,1] and [-1,-1,2].

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
• -105 <= nums[i] <= 105

Explanation/Approach

The problem is to find all unique triplets in the array that add up to zero. This problem can be efficiently solved using a combination of sorting and two-pointer technique.

• Sorting: First, we sort the array. This helps in skipping duplicates and also makes it easier to move pointers for checking sums.
• Iterating with a Fixed Element: We iterate through the array, fixing one element at a time and then using two pointers to find the other two elements.
• Two Pointers: For each fixed element, we use a left pointer starting right after the fixed element and a right pointer at the end of the array. We move these pointers based on the sum of the triplet.
• Skipping Duplicates: To avoid duplicate triplets, we skip over duplicate values both for the fixed element and while moving the two pointers.

Solution: Two Pointers with Sorting

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # Resultant list for storing triplets
        res = []

        # Sort the array to simplify finding triplets and avoiding duplicates
        nums = sorted(nums)

        # Iterate over the array
        for i, num1 in enumerate(nums):
            # If the current number is greater than 0, further triplets are impossible
            if num1 > 0:
                break

            # Skip duplicate elements
            if i > 0 and num1 == nums[i-1]:
                continue

            # Initialize two pointers
            l, r = i + 1, len(nums) - 1

            # Iterate with the two pointers
            while r > l:
                three_sum = num1 + nums[l] + nums[r]

                # Move pointers based on the sum
                if three_sum > 0:
                    r -= 1
                elif three_sum < 0:
                    l += 1
                else:
                    # Add the triplet to the result
                    res.append([num1, nums[l], nums[r]])
                    l += 1

                    # Skip duplicates for the left pointer
                    while nums[l] == nums[l-1] and l < r:
                        l += 1

        return res

Time and Memory Complexity

The time complexity is O(n^2), primarily due to the two-pointer traversal for each element. The sorting operation contributes O(n log n), which is overshadowed by the quadratic complexity. The space complexity is O(1) or O(n) depending on the implementation of the sorting algorithm.

Explanation

This solution begins by sorting the array. For each element (skipping duplicates), it looks for a pair in the rest of the array that adds up to the negative of the element. The two pointers (l and r) help in finding these pairs. When a triplet is found, it is added to the result, and the left pointer is moved while skipping over duplicates.

Visualization

You’re correct. Let’s adjust the visualization for Iteration 2 to reflect this step:

Visualization

With the sorted array [-4, -1, -1, 0, 1, 2] from nums = [-1,0,1,2,-1,-4], the algorithm’s process is as follows:

Iteration 1 (fix -4):
    Array: [-4, -1, -1, 0, 1, 2]
            ↑        ↑        ↑
    l = 1, r = 5. The sum is always less than 0, with the smallest sum being -3 (-4 + -1 + 2), so no valid triplet is found.

Iteration 2 (fix first -1):
    Array: [-4, -1, -1, 0, 1, 2]
                 ↑   ↑        ↑
    l = 2, r = 5. Initially, the sum is 0 (-1 + -1 + 2), finding a valid triplet [-1, -1, 2].
    After finding this triplet, we move the left pointer once to avoid duplicates:
    l = 3, r = 5. Now, the sum is 0 (-1 + 0 + 1), finding another valid triplet [-1, 0, 1].

Iteration 3 (skip second -1, duplicate):
    Skipping the second -1 to avoid repeating the same triplet.

Iteration 4 (fix 0):
    Array: [-4, -1, -1, 0, 1, 2]
                        ↑  ↑  ↑
    l = 4, r = 5. The sum is 3 (0 + 1 + 2), which is too large. Adjusting pointers does not find a valid triplet here.

Response:
    [[-1, -1, 2], [-1, 0, 1]]

In each iteration, the algorithm fixes one element (like -4, -1, 0) and uses two pointers (l and r) to find a pair in the rest of the array that adds up to the negative of the fixed element. After finding a valid triplet, the left pointer is moved to avoid duplicates and to find other possible combinations. Skipping duplicates is crucial to avoid repeating the same triplet and to enhance efficiency.