Domain 2MediumCORE

3Sum

We need to find all unique triplets within an integer array that sum up to zero. - Inputs: An unsorted list of integers nums. - Outputs: A list of lists, where each inner list represents a valid triplet [a, b, c] such that $a + b + c = 0$. - Constraints & Edge Cases: - The solution set must not contain duplicate triplets (e.g., [-1, 0, 1] is the same as [0, -1, 1]). - Indices of elements in a triplet must be distinct. - Input can include negative numbers and zeros. - Empty input or arrays with fewer than three elements should return an empty list immediately.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Two Pointers

15. 3Sum

Model: qwen3.5:9b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 28.3%


Problem Breakdown

We need to find all unique triplets within an integer array that sum up to zero.

  • Inputs: An unsorted list of integers nums.
  • Outputs: A list of lists, where each inner list represents a valid triplet [a, b, c] such that a+b+c=0a + b + c = 0.
  • Constraints & Edge Cases:
    • The solution set must not contain duplicate triplets (e.g., [-1, 0, 1] is the same as [0, -1, 1]).
    • Indices of elements in a triplet must be distinct.
    • Input can include negative numbers and zeros.
    • Empty input or arrays with fewer than three elements should return an empty list immediately.

Intuition

A naive brute-force approach uses three nested loops to check every combination (i,j,k)(i, j, k). This runs in O(N3)O(N^3) time complexity. Given the constraint nums.length <= 3000, this is too slow (27×10927 \times 10^9 operations).

To improve efficiency, we can fix one number and solve for a “Two Sum” problem on the remaining subarray.

  • Hashing Approach: Fix index ii, use a hash set to find pairs summing to -nums[i]. This is O(N2)O(N^2) time but requires O(N)O(N) extra space. Handling duplicates becomes messy because we need to track which indices were used and ensure unique triplets without storing too many states.
  • Two Pointers Approach: If we sort the array first, duplicate values are adjacent. We can fix index ii (the smallest number in a triplet) and use two pointers (left at i+1, right at end) to find pairs summing to -nums[i].
    • Since the array is sorted:
      • If current sum < target, we need a larger value →\rightarrow move left forward.
      • If current sum > target, we need a smaller value →\rightarrow move right backward.
      • This naturally handles duplicates by skipping identical values when moving pointers or iterating ii.

Sorting takes O(Nlog⁡N)O(N \log N), and the nested loop logic is effectively two passes over the array per outer iteration (O(N2)O(N^2)). The sorting step simplifies duplicate handling significantly compared to hashing.

Approach

  1. Sort nums in ascending order. This allows us to use binary search or two pointers and easily skip duplicates.
  2. Iterate through the array with index i. We stop at len(nums) - 3 because we need space for three elements (though iterating up to n-1 works if logic handles bounds).
    • Optimization: If nums[i] > 0, since the array is sorted, all subsequent numbers are positive. Their sum cannot be zero. Break early.
    • Duplicate Skip: If i > 0 and nums[i] == nums[i-1], skip this iteration to avoid generating duplicate triplets starting with the same number.
  3. Initialize two pointers: left = i + 1 and right = len(nums) - 1.
  4. While left < right:
    • Calculate sum of triplet.
    • If sum == 0: Add to results. Move both pointers inward (left++, right--). Crucially, skip any subsequent duplicate values for the new positions before continuing the loop check.
    • If sum < 0: Increment left (need larger sum).
    • If sum > 0: Decrement right (need smaller sum).

Complexity Analysis

  • Time Complexity: O(N2)O(N^2). Sorting takes O(Nlog⁡N)O(N \log N). The outer loop runs NN times, and the inner two-pointer scan is linear relative to the remaining elements. In worst case: ∑i=1N(N−i)=O(N2)\sum_{i=1}^{N} (N-i) = O(N^2).
  • Space Complexity: O(1)O(1) auxiliary space if we ignore the output list storage (Python’s Timsort uses O(N)O(N) stack, but typically interviewers focus on algorithmic logic). The result set size depends on input distribution.

Solution

def threeSum(nums):
    # Sort to handle duplicates and enable two-pointer technique
    nums.sort()
    
    n = len(nums)
    res = []
    
    for i in range(n - 2):
        # Optimization: If current number is positive, no solution possible 
        # because array is sorted (all subsequent numbers are >= current).
        if nums[i] > 0:
            break
        
        # Skip duplicates of the first element to avoid duplicate triplets
        if i > 0 and nums[i] == nums[i - 1]:
            continue
            
        left, right = i + 1, n - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            if current_sum == 0:
                res.append([nums[i], nums[left], nums[right]])
                
                # Skip duplicates for the second element (left)
                val_left = nums[left]
                while left < right and nums[left] == val_left:
                    left += 1
                
                # Skip duplicates for the third element (right)
                val_right = nums[right]
                while left < right and nums[right] == val_right:
                    right -= 1
                    
            elif current_sum < 0:
                left += 1
            else:
                right -= 1
                
    return res

Edge Cases Handled

  • Empty Array / Length < 3: The loop range(n - 2) handles this naturally (loop won’t execute), returning empty list.
  • All Positive Numbers: Optimization check (nums[i] > 0) breaks early, preventing unnecessary computation and correctly returning an empty result set if no zeros/negatives exist to balance positives.
  • Duplicate Values in Input: The logic explicitly skips i when it matches the previous element (outer loop) and skips subsequent identical elements for left/right pointers upon finding a match, ensuring unique triplets only.