3Sum

TypeArray, Two Pointers
Difficulty
Medium
Last Reviewed12/28/2024

Problem Description

Given an array nums of n integers, find all unique triplets in the array which gives the sum of zero. Each triplet must be a tuple of three elements and 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: In this example, the sum of the three elements at index (0, 1, 3) is 0. The sum of the three elements at index (1, 2, 3) is also 0.

Example 2

Input: nums = []

Output: []

Explanation: In this example, there are no elements in the input array, so there are no triplets that sum to zero.

Example 3

Input: nums = [0]

Output: []

Explanation: In this example, there is only one element in the input array, so there are no triplets that sum to zero.

Solution Overview

Initial Approach

Use a two-pointer approach to find all unique triplets in the array that sum up to zero.

Step by Step Solution

  1. Sort the array to simplify the two-pointer approach.
  2. Iterate through the array and fix the first element of the triplet.
  3. Use two pointers to find the other two elements that sum up to the negative of the fixed element.
  4. Skip duplicates to avoid duplicate triplets.
  5. Repeat the process until all triplets are found.

Solution Code

1# Sort the array to easily handle duplicates
2nums.sort()
3
4# Initialize the result array
5result = []
6
7# Iterate over each element in the array
8for i in range(len(nums) - 2):
9    # Skip duplicates
10    if i > 0 and nums[i] == nums[i - 1]:
11        continue
12    # Initialize left and right pointers
13    left, right = i + 1, len(nums) - 1
14    # Two-pointer approach
15    while left < right:
16        total = nums[i] + nums[left] + nums[right]
17        if total == 0:
18            result.append([nums[i], nums[left], nums[right]])
19            # Skip duplicates
20            while left < right and nums[left] == nums[left + 1]:
21                left += 1
22            while left < right and nums[right] == nums[right - 1]:
23                right -= 1
24            left += 1
25            right -= 1
26        elif total < 0:
27            left += 1
28        else:
29            right -= 1

Solution Walkthrough

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

Step 1

1nums.sort()

Sort the array to easily handle duplicates and for efficient traversal

State: Sorted nums: [-4, -1, -1, 0, 1, 2]

Step 2

1result = []

Initialize the result array to store triplets that sum up to zero

State: Sorted nums: [-4, -1, -1, 0, 1, 2] Result: []

Step 3

1for i in range(len(nums) - 2):

Iterate over each element until the third last element to avoid out of bounds

State: Sorted nums: [-4, -1, -1, 0, 1, 2] Result: [] i = 0

Step 4

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

Skip duplicates by checking if the current element is the same as the previous one

State: Sorted nums: [-4, -1, -1, 0, 1, 2] Result: [] i = 0 No duplicates skipped

Step 5

1left, right = i + 1, len(nums) - 1

Initialize left and right pointers for the two-pointer approach

State: Sorted nums: [-4, -1, -1, 0, 1, 2] Result: [] i = 0 left = 1, right = 5

Step 6

1total = nums[i] + nums[left] + nums[right]

Calculate the total sum of the triplet

State: Sorted nums: [-4, -1, -1, 0, 1, 2] Result: [] i = 0 left = 1, right = 5 Total: -4 + -1 + 2 = -3

Step 7

1if total == 0:
2    result.append([nums[i], nums[left], nums[right])
3    while left < right and nums[left] == nums[left + 1]:
4        left += 1
5    while left < right and nums[right] == nums[right - 1]:
6        right -= 1
7    left += 1
8    right -= 1

If the total sum is zero, add the triplet to the result and move pointers accordingly. Skip duplicates

State: Sorted nums: [-4, -1, -1, 0, 1, 2] Result: [[-1, -1, 2]] i = 0 left = 1, right = 5

Step 8

1elif total < 0:
2    left += 1

If the total sum is less than zero, move the left pointer to the right

State: Sorted nums: [-4, -1, -1, 0, 1, 2] Result: [[-1, -1, 2]] i = 0 left = 2, right = 5

Step 9

1else:
2    right -= 1

If the total sum is greater than zero, move the right pointer to the left

State: Sorted nums: [-4, -1, -1, 0, 1, 2] Result: [[-1, -1, 2]] i = 0 left = 2, right = 4

Complexity Analysis

Time Complexity: O(n^2)

The algorithm involves sorting the array and then iterating through each element and finding the other two elements using two pointers. This results in a quadratic time complexity.

Space Complexity: O(n)

We use a hash set to store the unique triplets, which has a space complexity of O(n) where n is the number of unique triplets.

Breakdown:

    Algorithmic Patterns

    Two Pointers

    How it's used: Finding pairs in sorted arrays or lists efficiently

    Where in code: Finding triplets that sum to zero

    Example: Given a sorted array, finding two elements that sum to a target value

    Common Mistakes

    Mistake 1

    What: Not handling duplicates properly in the solution

    Why: This can lead to incorrect outputs and missing valid triplets

    How to avoid: Use proper logic to skip duplicate elements while iterating over the array

    Mistake 2

    What: Not considering edge cases like empty input or input with less than 3 elements

    Why: This can cause errors or exceptions during the execution

    How to avoid: Always handle these edge cases at the beginning of the solution

    Mistake 3

    What: Using brute force algorithms that result in high time complexity

    Why: This can lead to inefficient solutions, especially for large input sizes

    How to avoid: Optimize the solution using two-pointer technique or a hashmap for efficient lookups

    Interview Tips

    • Understand the problem constraints and requirements clearly before starting
    • Consider sorting the input array to simplify the solution
    • Use a set or dictionary to store unique triplets to avoid duplicates