3 sum and 4 sum problem and solution in Java and Python

Let’s explore 3Sum and 4Sum — two classic interview problems that build on the Two Sum idea — step by step.

---

🎯 1. What Are 3Sum and 4Sum?

Both are extensions of the Two Sum problem.

Problem	Goal
Two Sum	Find 2 numbers that add up to a target
3Sum	Find 3 numbers that add up to a target (often 0)
4Sum	Find 4 numbers that add up to a target

---

🧩 Example — 3Sum

Input:

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

Output:

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

Explanation: Each triplet adds up to 0.

---

🧠 Intuition

You want all unique triplets (or quadruplets) whose sum = target.

Instead of checking all combinations (which would be slow — O(n³) for 3Sum), we use sorting + two-pointer technique to bring it down to O(n²).

---

⚙️ 3Sum — Step-by-Step

1. Sort the array → makes it easier to skip duplicates and use two pointers.

2. Fix one element (i) Then use two pointers (left, right) to find the remaining two numbers.

3. Move pointers based on the sum:

   • If sum < target → move left++
   • If sum > target → move right--
   • If sum == target → store the triplet and skip duplicates

---

💻 Java Implementation (3Sum)

import java.util.*;

public class ThreeSum {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate

            int left = i + 1, 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]));
                    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++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(nums));
    }
}

---

💻 Python Implementation (3Sum)

def threeSum(nums):
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result

print(threeSum([-1, 0, 1, 2, -1, -4]))

---

🧩 4Sum Problem

Same idea, but now we fix 2 elements and use the two-pointer method for the other two.

---

Example:

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

Output:

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

---

💻 Java — 4Sum

import java.util.*;

public class FourSum {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1, right = nums.length - 1;

                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++; right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 0, -1, 0, -2, 2};
        System.out.println(fourSum(nums, 0));
    }
}

---

💻 Python — 4Sum

def fourSum(nums, target):
    nums.sort()
    res = []
    n = len(nums)

    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left, right = j + 1, n - 1
            while left < right:
                s = nums[i] + nums[j] + nums[left] + nums[right]
                if s == target:
                    res.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif s < target:
                    left += 1
                else:
                    right -= 1
    return res

print(fourSum([1, 0, -1, 0, -2, 2], 0))

---

⚡ Key Differences

Feature	3Sum	4Sum
Fix	1 number	2 numbers
Time Complexity	O(n²)	O(n³)
Space Complexity	O(1) (ignoring result list)	O(1)
Typical Technique	Sorting + Two Pointers	Sorting + Nested Two Pointers

---

🧠 Real-Life Analogy

• Two Sum: You’re buying 2 fruits whose total cost matches your wallet.
• Three Sum: You’re buying 3 fruits with exact budget.
• Four Sum: You’re buying 4 fruits — combinations increase, so you need more loops!

---