15. 3Sum - Detailed Explanation

Problem Statement

Description:
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that:

• ( nums[i] + nums[j] + nums[k] = 0 )
• ( i ), ( j ), and ( k ) are distinct indices.

Note:

• The solution set must not contain duplicate triplets.
• The order of the triplets in the output does not matter.

Example Inputs, Outputs, and Explanations

1. Example 1:

   • Input: nums = [-1, 0, 1, 2, -1, -4]
   • Output: [[-1, -1, 2], [-1, 0, 1]]
   • Explanation:
     • The triplets that sum to zero are:
       • (-1 + (-1) + 2 = 0)
       • (-1 + 0 + 1 = 0)
     • Notice that duplicate triplets are not allowed.

2. Example 2:

   • Input: nums = []
   • Output: []
   • Explanation:
     • An empty array does not contain any triplets.

3. Example 3 (Edge Case):

   • Input: nums = [0]
   • Output: []
   • Explanation:
     • With fewer than three elements, no triplet can be formed.

Constraints

• ( 0 \leq \text{nums.length} \leq 3000 )
• ( -10^5 \leq \text{nums}[i] \leq 10^5 )

Hints to Approach the Solution

1. Sorting Is Key:

   • Sorting the array helps to avoid duplicates and makes it easier to use two pointers to find pairs that sum to a specific target.

2. Two-Pointer Technique:

   • For each element ( nums[i] ) in the sorted array, use two pointers (one starting just after ( i ) and one at the end) to search for a pair such that their sum equals ( -nums[i] ).

3. Skip Duplicates:

   • To ensure unique triplets, skip over duplicate elements when iterating through the array and when moving the two pointers.

Approach 1: Brute Force (Not Recommended)

Explanation

• Method:
  • Use three nested loops to check every possible triplet in the array.
• Drawbacks:
  • Time complexity is ( O(n^3) ), which is not efficient for larger arrays.

Approach 2: Sorting with Two-Pointer Technique (Optimal)

Explanation

• Step 1: Sort the Array
  • Sorting helps in identifying duplicates and simplifies the two-pointer search.
• Step 2: Iterate Through the Array
  • For each index ( i ) (from 0 to ( n-3 )):
    • If ( i > 0 ) and ( nums[i] ) is the same as ( nums[i-1] ), skip it to avoid duplicates.
• Step 3: Two-Pointer Search
  • Initialize two pointers:
    • ( \text{left} = i + 1 )
    • ( \text{right} = n - 1 )
  • While ( \text{left} < \text{right} ):
    • Compute ( \text{sum} = nums[i] + nums[left] + nums[right] )
    • If ( \text{sum} == 0 ):
      • Add the triplet to the result.
      • Skip duplicates for both ( \text{left} ) and ( \text{right} ).
      • Move both pointers inward.
    • If ( \text{sum} < 0 ):
      • Increase ( \text{left} ) (to add a larger number).
    • If ( \text{sum} > 0 ):
      • Decrease ( \text{right} ) (to add a smaller number).

Pseudocode

sort(nums)
result = []
for i from 0 to len(nums) - 3:
    if i > 0 and nums[i] == nums[i - 1]:
        continue
    left = i + 1, right = len(nums) - 1
    while left < right:
        sum = nums[i] + nums[left] + nums[right]
        if sum == 0:
            add triplet [nums[i], nums[left], nums[right]] to result
            while left < right and nums[left] == nums[left + 1]:
                left++
            while left < right and nums[right] == nums[right - 1]:
                right--
            left++, right--
        else if sum < 0:
            left++
        else:
            right--
return result

Code Implementations

Python Code

Complexity Analysis

• Time Complexity:

  • Sorting the array takes ( O(n \log n) ).
  • The main loop runs in ( O(n^2) ) in the worst case (using two pointers inside the loop).
  • Overall: ( O(n^2) ).

• Space Complexity:

  • ( O(1) ) extra space aside from the space needed to store the output.
  • Sorting is typically done in-place.

Step-by-Step Walkthrough (Visual Example)

Consider the input:

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

1. Sort the Array:
   Sorted nums = [-4, -1, -1, 0, 1, 2].

2. Iteration:

   • i = 0: ( nums[0] = -4 )
     • Set ( left = 1 ) and ( right = 5 ).
     • Check sum: (-4 + (-1) + 2 = -3) (less than 0) → move left pointer.
     • Continue: (-4 + (-1) + 2 = -3) → still less than 0.
     • No valid triplet found for ( i = 0 ).
   • i = 1: ( nums[1] = -1 )
     • Set ( left = 2 ) and ( right = 5 ).
     • Check sum: (-1 + (-1) + 2 = 0) → valid triplet found: ([-1, -1, 2]).
     • Skip duplicate for ( left ) and move pointers.
     • Next, check: (-1 + 0 + 1 = 0) → valid triplet found: ([-1, 0, 1]).

3. Result:
   The valid triplets found are:
   ([[-1, -1, 2], [-1, 0, 1]]).

Common Mistakes & Edge Cases

Common Mistakes

• Duplicates:
  • Failing to skip over duplicates when moving the pointers or iterating the main loop may lead to repeated triplets.
• Pointer Mismanagement:
  • Incorrectly updating the ( left ) and ( right ) pointers might result in missing valid triplets or including invalid ones.
• Boundary Conditions:
  • Not handling arrays with fewer than three elements correctly.

Edge Cases

• Empty Array or Array with Fewer than 3 Elements:
  • Return an empty list.
• All Zeros:
  • Ensure only one triplet ([0, 0, 0]) is returned, even if there are multiple zeros.
• No Valid Triplet:
  • If no triplet sums to zero, return an empty list.

Alternative Variations and Related Problems

Variations

• 4Sum:
  • Find all unique quadruplets that sum up to a target value.
• 3Sum Closest:
  • Find the triplet whose sum is closest to a given target.

Related Problems for Further Practice

• 4Sum
• 3Sum Closest
• Two Sum