Solving the 4Sum Problem in Java

Want to crack coding interviews? The 4Sum problem builds logic, speed, and clean thinking.

Solving DSA problems helps us think clearly and build strong problem-solving skills. It also makes us better at writing fast and efficient code for real-world applications.

In this blog post, we'll break down the 4Sum problem, understand the logic, and walk through a clean Java implementation that handles edge cases and avoids duplicates efficiently.

Problem Statement

Given an array nums of n integers, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that it follows the points below, and we can return the result in any order:

• 0 <= a, b, c, d < n
• All indices are distinct
• nums[a] + nums[b] + nums[c] + nums[d] == target

Constraints:

• 1 <= nums.length <= 200
  
• -109 <= nums[i] <= 109
• -109 <= target <= 109

Intuition

If we’ve solved the 3Sum problem, it helps us understand the 4Sum problem better. We already know how to use sorting, two pointers, and how to skip duplicates — the same ideas work here too.

To solve this problem, we first sort the array, get two numbers of a combination using two nested for loops, and then apply two pointers to get the rest of the two numbers. We skip duplicate numbers in each loop level and use long to avoid integer overflow.

Java Implementation

So below is the code of Java implementation of solving this problem by applying the above concepts:

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList();
    int n = nums.length;
     
    Arrays.sort(nums);
    for(int i=0; i<n-3;i++){
        if(i>0 && nums[i] == nums[i-1]) continue;
        for(int j=i+1;j<n-2;j++){
            if(j>i+1 && nums[j] == nums[j-1]) continue;
            int left = j + 1;
            int right = n - 1;

            while(left<right){
                long sum = (long) nums[i]+nums[j]+nums[left]+nums[right];
                if(sum == target){
                    result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));

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

                    left++;
                    right--;
                }else if(sum < target) left++;
                else right--;
            }
        }
    }
    return result;
}

In the above example, we have used the same logic as the 3Sum problem, just adding one more nested loop. The time and space complexity of this solution are O(n^3) and O(1).

Now we have successfully solved this problem with the two-pointer approach. Two pointers are used in many DSA problems, and mastering it helps us solve many of them.

I hope you enjoyed solving the 4Sum problem with me, understood the logic step by step, saw how sorting and two pointers work together, and found this post helpful in building your DSA skills.

Thanks for reading! 🤝 Happy Coding! ✨