4Sum Problem

You're planning your dream vacation. You've got a budget to stick to, a bunch of activities to choose from, and a challenge: you want to pick exactly 4 activities such that their total cost matches your exact travel budget.

Sound familiar? Welcome to the world of the 4Sum problem — but make it tropical. 🌴

🗺️ The Vacation Challenge

Here’s what you're working with:

• A list of activities, each with its own cost.
• You want to pick 4 distinct activities.
• The total cost of the 4 must match your travel budget (target).
• And oh — no repeated plans! No duplicate combinations, even if the order changes.

🧾 Problem Statement

Given: An array of integers nums (activity costs) and an integer target (your budget).

Return: All unique quadruplets [a, b, c, d] such that:

nums[a] + nums[b] + nums[c] + nums[d] == target

You can return the results in any order, but all sets must be distinct.

🎒 Packing Strategy

Let’s break it down:

1. Sort the activities. Makes duplicates easier to skip and helps use pointers smartly.
2. Use two fixed positions (like your must-do activities).
3. Use two pointers (left and right) to find the remaining two that make the budget work.
4. Skip duplicate activities to keep your itinerary unique.
5. When the sum is too low, increase the left pointer (pick pricier activities).
6. When the sum is too high, decrease the right pointer (go cheaper).

Basically — it's like scrolling through a travel app, narrowing down 4 perfect plans that hit the sweet spot in price ✨.

💻 The Code

class Solution {

public List<List<Integer>> fourSum(int[] nums, int target) {

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

Arrays.sort(nums); // Sort the array first

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

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

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

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

int left = j + 1;

int right = nums.length - 1;

while (left < right) {

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

if (sum == target) {

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

// Skip duplicates for left and right pointers

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++; // Need a larger number

} else {

right--; // Need a smaller number

}

}

}

}

return result;

}

}

🕹️ Time & Space Complexity Breakdown

⏰ Time Complexity

The time complexity is a combination of multiple factors:

1. Sorting takes 𝑂(𝑛 log 𝑛) time.

2. The two outer loops (i and j) iterate over the array with the following structure:

• The outer loop (i) runs 𝑂(𝑛) times.
• The second loop (j) runs 𝑂(𝑛) times for each i, resulting in 𝑂(𝑛^2) iterations in total.

3. The two pointers (left and right) together cover the remaining elements, and in the worst case, this is 𝑂(𝑛) for each pair of i and j.

Therefore, the overall time complexity is 𝑂(𝑛^3), which is significantly better than the brute force 𝑂(𝑛^4) solution.

💾 Space Complexity

The space complexity is 𝑂(𝑘), where 𝑘 is the number of unique quadruplets found. This is because we need space to store the results, and the amount of space depends on how many quadruplets are returned.

🏝️ Final Thoughts

And there you have it! 🌟 With this approach, you're able to narrow down your vacation plans to the perfect four activities that fit within your budget, avoiding the stress of too many options. By sorting the activities and using two pointers, you can efficiently find the ideal combination of plans — all while keeping things distinct and optimized. Happy planning! ✈️🌴