LeetCode Medium Challenge Day 32 | 4Sum

Four Sum - LeetCode Problem

Problem Statement:

Given an array of integers nums and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < nums.length
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

The solution should avoid duplicate quadruplets.

Explanation:

This problem is an extension of the well-known "3Sum" problem and can be solved efficiently using a similar two-pointer technique after sorting the array. Here's the approach:

1. Sort the Array: Sorting helps in easily skipping duplicates and applying the two-pointer technique.
2. Iterate with Two Loops: The outer loop runs over the first element i, and the inner loop over the second element , We skip duplicate elements to ensure that each quadruplet is unique.
3. Two-Pointer Technique: For each pair (i, j), we use two pointers (left and right) to find pairs that sum up to the target by checking if the current sum matches the target. If the sum is less than the target, we move the left pointer to the right to increase the sum. If the sum is greater than the target, we move the right pointer to the left to decrease the sum.
4. Avoid Duplicates: Skip duplicates after finding a valid quadruplet by moving pointers to the next unique elements

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

        int n = nums.length;  

        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] + (long) nums[j] + (long) nums[left] + (long) nums[right];  
                    if (sum == target) {  
                        quadruplets.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 quadruplets;  
    }
}