3Sum Problem

🧩 What's the Problem?

You're at your favorite online store. You've added a bunch of items to your cart, applied a couple of gift cards and discount coupons — but you want to balance your checkout perfectly. That means:

Pick any three things — products, gift cards, or coupons — whose total value adds up to zero.

Some items cost you money (+ve), others give you money back like cashback or gift cards (-ve), and some are free (0).

So your goal is:

🎯 Find all unique combinations of 3 items where the total cost is zero.

🧪 Example

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

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

• One combo: -1 (discount) + -1 (gift card) + 2 (expensive item) = 0
• Another combo: -1 + 0 + 1 = 0
• Triplets like [0, 1, -1] are considered duplicates of [–1, 0, 1], so we don’t count them twice.

🛠️ How Do We Solve It?

Let’s say you have a cart with n items. Checking all combinations of 3 manually would take O(n³) time (slow). We want a smarter way — and that’s where sorting and two pointers come in.

Think of it like this:

🛒 Step-by-Step Shopping Strategy:

1. Sort the cart items.

- That way, your costs and discounts are in order — like neatly arranging your cart.

2. Fix the first item (let’s call it i) — like picking the first thing you’re sure you want.

3. Now, you need two more items that will cancel out the cost of the first one.

- So the new target becomes: 0 - nums[i].

4. Use a two-pointer approach to find this pair:

• left starts just after i
• right starts at the end

5. Move the pointers smartly:

• If the sum is too low → move left up
• If it’s too high → move right down
• If it’s just right → bingo! Add the triplet

6. Skip duplicates so we don’t end up with repeated combos.

📦 The Code (Java)

class Solution {

public List<List<Integer>> threeSum(int[] nums) {

List<List<Integer>> result = new ArrayList<>();

Arrays.sort(nums); // Step 1: Sort your cart

for (int i = 0; i < nums.length - 2; i++) {

if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates

int left = i + 1;

int right = nums.length - 1;

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];

if (sum == 0) {

result.add(Arrays.asList(nums[i], nums[left], nums[right]));

// Skip duplicates

while (left < right && nums[left] == nums[left + 1]) left++;

while (left < right && nums[right] == nums[right - 1]) right--;

left++;

right--;

} else if (sum < 0) {

left++; // Need a bigger number

} else {

right--; // Need a smaller number

}

}

}

return result;

}

}

Walkthrough Example — Let’s Shop!

Input:

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

Step 1: 🧹 Sort the prices

Sorting helps organize our search and avoid duplicate bundles.

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

Step 2: Try each item as the first pick

We fix one item at a time (index i) and use two pointers (left and right) to find two other items such that their total is zero.

🔷 i = 0 → nums[i] = -4

• left = 1 (nums[left] = -1), right = 5 (nums[right] = 2)
• Total = -4 + (-1) + 2 = -3 → too low

➡️ Move left → left = 2 (nums[left] = -1)

• Total = -4 + (-1) + 2 = -3 → still too low

➡️ Move left → left = 3 → left >= right → Stop

🛑 No valid bundle with -4

🔷 i = 1 → nums[i] = -1

• left = 2 (nums[left] = -1), right = 5 (nums[right] = 2)
• Total = -1 + (-1) + 2 = 0 ✅

🎉 Found triplet: [-1, -1, 2]

➡️ Move left to 3, right to 4

• New Total = -1 + 0 + 1 = 0 ✅

🎉 Found triplet: [-1, 0, 1]

➡️ Move left to 4, right to 3 → Stop

🔷i = 2 → nums[i] = -1 again → ❌ skip duplicate

🔷 i = 3 → nums[i] = 0

• left = 4 (1), right = 5 (2)
• Total = 0 + 1 + 2 = 3 → too high

➡️ Move right to 4 → left >= right → Stop

🛑 No valid bundle with 0

✅ Final Answer:

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

📊 Time and Space Complexity

1. Time Complexity:

• Sorting the array takes O(n log n).
• For each element, we perform a two-pointer search in O(n) time.
• The overall time complexity is O(n²).

2. Space Complexity:

• We are using extra space to store the result (which can contain up to O(n) triplets).
• Therefore, the space complexity is O(n).

📚 Key Takeaways:

1. Sort first, then search:

Sorting the array helps organize the search and avoid duplicates.

2. The two-pointer trick:

Use the two-pointer approach after fixing one element. It makes finding the right pair much more efficient.

3. Skip duplicates:

After finding a valid triplet, skip the same combinations to keep your results unique.

4. Efficiency over brute force:

This approach reduces the problem's time complexity from O(n³) to O(n²), making it much more efficient.