3Sum | Leetcode 15 | Explained in Python

LeetCode #15 “3Sum” asks you to find all unique triplets (i, j, k) in an integer array such that

nums[i] + nums[j] + nums[k] == 0              (i < j < k)

The answer must exclude duplicates, but the order within each triplet or across triplets does not matter.

Example
Input nums = [-1, 0, 1, 2, -1, -4]
Output [[-1, -1, 2], [-1, 0, 1]]

Why it matters: 3Sum is a classic interview favorite that highlights hashing, two-pointer techniques, and duplicate-handling strategies.

Here’s the [Problem Link] to begin with.

Brute Force Solution (Triple Nested Loops)

Intuition & Approach

The most literal idea is to test every possible triplet.
For each combination (i, j, k):

1. Check if their sum is zero.
2. Sort the triplet so [a, b, c] and [b, a, c] look identical.
3. Store it in a set (of tuples) to eliminate duplicates automatically.

Code Implementation

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        my_set = set()
        n = len(nums)

        # check all possible triplets
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    # if the current triple sums to zero
                    if nums[i] + nums[j] + nums[k] == 0:
                        temp = [nums[i], nums[j], nums[k]]
                        temp.sort()          # sort to avoid order duplicates
                        my_set.add(tuple(temp))

        # convert set of tuples back to list of lists for the answer
        ans = [list(item) for item in my_set]
        return ans

Code Explanation

• Three nested loops explore all n · (n-1) · (n-2) / 6 triplets.
• Sorting each hit guarantees [2, -1, -1] and [-1, 2, -1] merge into the same key.
• Set ensures uniqueness; we convert back to list before returning.

Dry Run

Using [-1, 0, 1]:

Every other combination fails or repeats, so the final answer is [-1,0,1].

Time & Space Complexity

• Time: O(n³) – impractical beyond ~300 numbers.
• Space: O(t) where t = #unique triplets (≤ n³) plus loop variables.

Conclusion

Good for understanding the problem’s essence, but far too slow for real data sets or interviews.

Better Solution (Hash-Set per Fixed Index)

Intuition & Approach

Fix one number nums[i], then the problem reduces to 2Sum = -nums[i] inside the suffix (i+1 … n-1).

• Maintain a hash set recording numbers we’ve seen in the inner loop.
• If third = - (nums[i] + nums[j]) is already in the set, we’ve found a triplet.
• Again sort & store in a global set to avoid duplicates.

Code Implementation

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = set()  # stores unique sorted triplets

        for i in range(n):
            hashset = set()   # fresh set for each fixed i
            for j in range(i + 1, n):
                third = -(nums[i] + nums[j])  # value we need
                if third in hashset:
                    temp = [nums[i], nums[j], third]
                    temp.sort()
                    result.add(tuple(temp))
                # add current nums[j] for future pairs
                hashset.add(nums[j])

        ans = list(result)
        return ans

Code Explanation

• Outer loop picks every possible first element.
• Inner loop simultaneously checks for complements while recording seen numbers in hashset.
• Each hashset is reset for a new i so only suffix elements pair with it.

Dry Run (Short Example)

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

1. i = 0 (nums[i] = -1)
   • j = 1: need 1; hashset = {0} → not found
   • j = 2: need 0; hashset has 0 → triplet [-1, 0, 1] stored
   • j = 3: need -1; not found
2. Further i values may find more triplets (none in this short array).

Time & Space Complexity

• Time: O(n²) – outer n times inner n/2 on average.
• Space: O(n) – the per-iteration hashset.

Conclusion

The hash-set technique crushes one loop and becomes feasible for arrays in the low-thousands, yet still incurs overhead from repeated set allocations.

Optimal Solution (Sorting + Two Pointers)

Intuition & Approach

1. Sort nums.
2. For each index i (skipping duplicates):
   • Target sum becomes -nums[i].
   • Use two pointers j = i+1, k = n-1 to search the remaining sub-array for pairs adding to the target.
   • On a hit, move both pointers inward while skipping duplicates to keep results unique.

Sorting lets identical numbers group together, simplifying duplicate elimination and enabling the two-pointer sweep in linear time per fixed i.

Code Implementation

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        nums.sort()  # sort first for two-pointer technique

        for i in range(n):
            # skip duplicate fixed elements
            if i != 0 and nums[i] == nums[i - 1]:
                continue

            # set up the two pointers
            j = i + 1
            k = n - 1

            # move pointers toward each other
            while j < k:
                total_sum = nums[i] + nums[j] + nums[k]

                if total_sum < 0:
                    j += 1                     # need a larger sum
                elif total_sum > 0:
                    k -= 1                     # need a smaller sum
                else:
                    # found a valid triplet
                    temp = [nums[i], nums[j], nums[k]]
                    ans.append(temp)

                    # move both pointers and skip duplicates
                    j += 1
                    k -= 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1

        return ans

Code Explanation

• Sorting is the only extra cost and makes duplicate handling trivial.
• Pointer Logic
  • total_sum too small ⇒ increment j to pick a larger number.
  • total_sum too big ⇒ decrement k for a smaller number.
  • Hit ⇒ record and move both pointers while skipping repeated values.
• Duplicate-Skip Guard at the top ensures each distinct nums[i] is processed once.

Dry Run (Classic Example)

Sorted array: [-4, -1, -1, 0, 1, 2]

Pointers cross → finish.

Time & Space Complexity

• Time: O(n²) overall (O(n log n) sort + O(n²) scan), but with a very low constant – fastest practical approach.
• Space: O(1) extra (ignoring output) thanks to in-place sorting.

Conclusion

The two-pointer strategy after sorting is the gold-standard answer in interviews: clean, efficient, and no hashing overhead. Mastering its duplicate-skip nuances is key to flawless implementation.

Final Thoughts

• Brute: easiest to code, worst performance (O(n³)).
• Better (Hash-set): big speedup (O(n²)) but still rebuilds sets.
• Optimal (Sort + Two Pointers): same O(n²) time yet fastest in practice with O(1) extra space.

Remember these three tiers, exhaustive, hashing, two-pointers, and you’ll be ready for not only 3Sum but a family of k-sum problems that build on these very ideas. Happy coding!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.