LeetCode Solution: 15. 3Sum

#leetcode #dsa #programming #tutorial

Cracking the Code: Solving LeetCode's 3Sum Problem with Two Pointers 🟡 Medium

Hey there, fellow coders! 👋 Today, we're diving into a classic LeetCode problem that might seem daunting at first glance but becomes a satisfying puzzle with the right approach: 15. 3Sum. It's a fantastic problem to sharpen your problem-solving skills, especially with arrays and pointers.

Problem Explanation

We're given an array of integers, nums. Our mission is to find all unique triplets [nums[i], nums[j], nums[k]] such that:

i, j, and k are distinct indices (meaning i != j, i != k, and j != k).
The sum of the three numbers nums[i] + nums[j] + nums[k] equals zero.
The final solution set must not contain duplicate triplets. For example, [-1, 0, 1] and [0, -1, 1] are considered the same triplet.

Let's look at an example:

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

Here, we need to find three numbers that add up to 0. Some possibilities are:

(-1) + 0 + 1 = 0 (indices 0, 1, 2)
(-1) + 2 + (-1) = 0 (indices 0, 3, 4)

The distinct triplets in the output would be [[-1,-1,2], [-1,0,1]].

Constraints are also important:

The array will have between 3 and 3000 elements.
Numbers range from -10^5 to 10^5.

Intuition

First thoughts often lead to brute force: three nested loops to check every possible combination of i, j, and k. This would be an O(N^3) solution, which is usually too slow for arrays up to 3000 elements (3000^3 is huge!). We need a smarter way.

What if we could fix one number and then find two others? This reminds us of the "Two Sum" problem! If we fix nums[i], we then need to find two other numbers, nums[j] and nums[k], such that nums[j] + nums[k] = -nums[i].

How can we efficiently find two numbers that sum to a target? This is where sorting and the Two-Pointer technique shine!

Approach

Here's the step-by-step breakdown of an efficient approach:

Sort the Array:
- This is the cornerstone. Sorting nums allows us to easily move pointers and efficiently skip duplicate numbers. It also makes it simple to adjust our sum (if it's too small, increase a number; if too large, decrease a number).
Iterate and Fix the First Element (nums[i]):
- We'll use a single loop (for i in range(n)) to pick the first number of our potential triplet.
- Skip Duplicates for nums[i]: Since we want unique triplets, if nums[i] is the same as the previous nums[i-1], we've already considered all triplets starting with nums[i-1]. So, we can continue to the next i. This is crucial for avoiding duplicate triplets like [-1, 0, 1] and [-1, 0, 1] if -1 appears multiple times at the start of the array.
Use the Two-Pointer Technique for the Remaining Two Elements:
- Once nums[i] is fixed, our target sum for the remaining two numbers nums[j] and nums[k] becomes target = -nums[i].
- Initialize two pointers: j starting at i + 1 (the element right after nums[i]) and k starting at n - 1 (the last element of the array).
- Enter a while j < k loop:
  - Calculate the current_sum = nums[j] + nums[k].
  - If current_sum < target: The sum is too small. To increase the sum, we need a larger number. Since the array is sorted, increment j (move the left pointer to the right).
  - If current_sum > target: The sum is too large. To decrease the sum, we need a smaller number. Decrement k (move the right pointer to the left).
  - If current_sum == target: We found a triplet! [nums[i], nums[j], nums[k]]. Add it to our ans list.
    - Then, we need to move both pointers to find other potential triplets. Increment j and decrement k.
    - Skip Duplicates for nums[j] and nums[k]: After finding a valid triplet, nums[j] and nums[k] might have duplicates. To ensure unique triplets, we need to advance j as long as nums[j] is equal to the previous nums[j-1], and similarly for k (as long as nums[k] is equal to nums[k+1]).

This combined strategy transforms an O(N^3) brute force into a much more efficient O(N^2) solution!

Code

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        ans = []
        n = len(nums)
        nums.sort() # Step 1: Sort the array

        for i in range(n): # Step 2: Iterate fixing the first element
            # Skip duplicate for the first element
            # We check i > 0 to avoid index out of bounds on the first element
            if i > 0 and nums[i] == nums[i-1]:
                continue

            j = i + 1 # Left pointer starts after i
            k = n - 1 # Right pointer starts at the end of the array

            # Step 3: Two-pointer approach
            while j < k:
                total_sum = nums[i] + nums[j] + nums[k]

                if total_sum < 0:
                    j += 1 # Need a larger sum, move left pointer right
                elif total_sum > 0:
                    k -= 1 # Need a smaller sum, move right pointer left
                else: # total_sum == 0, found a triplet!
                    ans.append([nums[i], nums[j], nums[k]])

                    # Move pointers and skip duplicates for j and k
                    j += 1
                    k -= 1
                    # Skip duplicates for j
                    while j < k and nums[j] == nums[j-1]:
                        j += 1
                    # Skip duplicates for k
                    while j < k and nums[k] == nums[k+1]:
                        k -= 1
        return ans

Time & Space Complexity Analysis

Time Complexity:
- Sorting the array: This takes O(N log N) time.
- Outer loop (for i): This loop runs N times.
- Inner while loop (Two Pointers j and k): In the worst case, the j and k pointers traverse the remaining array once for each i. This takes O(N) time.
- Skipping duplicates: These while loops also run at most N times in total across all j and k movements for a fixed i.
- Combining these, the dominant part is N (for i) multiplied by N (for j and k traversal), which is O(N^2).
- Therefore, the total time complexity is O(N log N + N^2), which simplifies to O(N^2).
Space Complexity:
- Sorting: Python's list.sort() typically uses Timsort, which can take O(N) auxiliary space in the worst case (though often less). If we consider the algorithm itself beyond the standard library sort implementation, an in-place sort would be O(1) auxiliary space.
- Result list (ans): The space required to store the output triplets depends on the number of unique triplets. In the worst case, this could be O(N^2). However, typically, when we talk about space complexity, we're referring to auxiliary space used by the algorithm, not including the input or the required output.
- Excluding the output, the auxiliary space complexity is primarily due to sorting, which is O(N) for Python's default sort, or O(log N) for certain in-place sorts.

Key Takeaways

Sort First! For many array problems involving searching for combinations or manipulating relative order, sorting is often the key preprocessing step.
Two Pointers for Sorted Arrays: This technique is a workhorse! It efficiently finds pairs or helps reduce search space in sorted arrays.
Handle Duplicates Carefully: Unique results often mean adding extra checks to skip elements that would lead to redundant calculations or duplicate outputs. This is a common pitfall in these types of problems.

Submission Details

Authored by: p1Hzd8mRM8
Published: 2026-05-31 22:23:04

That's it for 3Sum! This problem is a fantastic way to practice combining sorting with the two-pointer technique and mastering duplicate handling. Keep coding, and happy problem-solving! ✨